hdu2203亲和串(kmp)

2024-06-12 00:08
文章标签 kmp hdu2203 亲和串

本文主要是介绍hdu2203亲和串(kmp),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

亲和串

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6610    Accepted Submission(s): 2988


Problem Description
人随着岁数的增长是越大越聪明还是越大越笨,这是一个值得全世界科学家思考的问题,同样的问题Eddy也一直在思考,因为他在很小的时候就知道亲和串如何判断了,但是发现,现在长大了却不知道怎么去判断亲和串了,于是他只好又再一次来请教聪明且乐于助人的你来解决这个问题。
亲和串的定义是这样的:给定两个字符串s1和s2,如果能通过s1循环移位,使s2包含在s1中,那么我们就说s2 是s1的亲和串。

Input
本题有多组测试数据,每组数据的第一行包含输入字符串s1,第二行包含输入字符串s2,s1与s2的长度均小于100000。

Output
如果s2是s1的亲和串,则输出"yes",反之,输出"no"。每组测试的输出占一行。

Sample Input
  
AABCD CDAA ASD ASDF

Sample Output
  
yes no

思路是把s1加倍,然后显然的kmp模板题;
注意加倍的操作,不可以strcat(text,text), 需要借助一个tep的数组


#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100005;
char pattern[MAXN];
char text[MAXN*2];
int next[MAXN];
char tep[MAXN];void get_next(){int m = strlen(pattern);next[0] = next[1] = 0;for(int i=1; i<m; i++){int j = next[i];while(j && pattern[i]!=pattern[j]) j=next[j];next[i+1] = (pattern[i]==pattern[j]? j+1 : 0);}
}void kmp(){int m = strlen(pattern);int n = strlen(text);int j=0;for(int i=0; i<n; i++){while(j && text[i]!=pattern[j]) j=next[j];if(text[i]==pattern[j]) j++;if(j==m){cout<<"yes"<<endl;return;}}cout<<"no"<<endl;
}
int main()
{while(cin>>text>>pattern){strcpy(tep,text);strcat(text,tep);get_next();kmp();}return 0;
}



这篇关于hdu2203亲和串(kmp)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1052633

相关文章

codeforces535D:Tavas and Malekas(KMP)

(i-1 , i)有重合的时候 ,从第i位开始的子串必须是模式串的前缀。 而同时,从第i位开始的子串本来就已经是模式串的后缀了。 typedef long long LL ;const int maxn = 1000008 ;int next[maxn] ;void getnext(char s[]){int len = strlen(s) ;next[0] = -1 ;i

fzu 2275 Game KMP

Problem 2275 Game Time Limit: 1000 mSec    Memory Limit : 262144 KB  Problem Description Alice and Bob is playing a game. Each of them has a number. Alice’s number is A, and Bob’s number i

KMP 详解

KMP数组存的是什么 对于一个字符串 b,下标从1开始。 则kmp[i]表示 以i结尾的连续子串 = s的前缀的最大值(等价于前缀最大结尾处) 如何求KMP 假设 i 以前的KMP都被求出来了。 j 表示上一个字符可以成功匹配的长度(等价于下标) 如果b[j+1] != b[i]下一个位置匹配不上(即不能成为前缀) 则,让j = kmp[j] 即成为以j结尾的 连续子串 的 最长前缀

KMP算法详解 --- 彻头彻尾理解KMP算法

前言     之前对kmp算法虽然了解它的原理,即求出P0···Pi的最大相同前后缀长度k。   但是问题在于如何求出这个最大前后缀长度呢?   我觉得网上很多帖子都说的不是很清楚,总感觉没有把那层纸戳破,   后来翻看算法导论32章 字符串匹配,虽然讲到了对前后缀计算的正确性,但是大量的推理证明不大好理解,没有与程序结合起来讲。   今天我在这里讲一讲我的一些理解,希望大家多多指教

扩展KMP --- HDU 3613 Best Reward

Best Reward Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=3613   Mean:  给你一个字符串,每个字符都有一个权值(可能为负),你需要将这个字符串分成两个子串,使得这两个子串的价值之和最大。一个子串价值的计算方法:如果这个子串是回文串,那么价值就是这个子串所有字符权值之和;否则价值为0。

数据结构串的实现以及KMP改进算法

</pre><pre name="code" class="cpp">#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 40 /* 存储空间初始分配量 */typedef int Status; /* Status是

字符串匹配算法之KMP算法和BM算法

[尊重原创]-原文链接在这里->http://blogread.cn/it/article/3975?f=wb 本文主要介绍KMP算法和BM算法,它们分别是前缀匹配和后缀匹配的经典算法。所谓前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从左到右;所谓后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右。看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同。下文分别

KMP算法 KMP模式匹配 二(串)

B - KMP模式匹配 二(串) Crawling in process... Crawling failed Time Limit:1000MS     Memory Limit:131072KB     64bit IO Format:%lld & %llu Description 输入一个主串和一个子串,用KMP进行匹配,问进行几趟匹配才成功,若没成功,则输出0

HDU 1358(kmp)

题意:给出一个数字n,接下来一行是一个字符串,n是这个字符串的长度。求这个字符串的所有是循环字符串的前缀。 kmp中的next数组只得是第i个字符匹配错误,向前跳的位置next【i】。   #include<algorithm>#include<stdio.h>#include<string>#include<string.h>#include<math.h>#include<qu

【HDU2087】【KMP】

剪花布条 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11677    Accepted Submission(s): 7509 Problem Description 一块花布条,里面有些图案,另有一块