首页 > 代码库 > HDU 2203 亲和串(KMP)
HDU 2203 亲和串(KMP)
题目网址:http://acm.hdu.edu.cn/showproblem.php?pid=2203
题目:
亲和串
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14720 Accepted Submission(s):
6505
Problem Description
人随着岁数的增长是越大越聪明还是越大越笨,这是一个值得全世界科学家思考的问题,同样的问题Eddy也一直在思考,因为他在很小的时候就知道亲和串如何判断了,但是发现,现在长大了却不知道怎么去判断亲和串了,于是他只好又再一次来请教聪明且乐于助人的你来解决这个问题。
亲和串的定义是这样的:给定两个字符串s1和s2,如果能通过s1循环移位,使s2包含在s1中,那么我们就说s2 是s1的亲和串。
亲和串的定义是这样的:给定两个字符串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和s2的长度,如果s1的长度小于s2,则直接输出no。否则做以下操作:s1[i+len]=s1[i],len为s1的长度。即从s[len]…s[2*len-1]又是一个s1。这样一个长度为2*len的新字符串包括了s1循环移位的所有情况,然后再在s1里找子串s2。因为字符串的长度比较大,所以传统的字符串匹配会超时,可以用strstr(),或者kmp。
代码:
1 #include <cstdio> 2 #include <cstring> 3 const int N=100005; 4 char str[2*N]; 5 char sub[N]; 6 int next[N]; 7 int ok; 8 void makeNext(){ 9 int l=strlen(sub); 10 next[0]=0; 11 for(int i=1,k=0; i<l; i++){ 12 while(k>0 && sub[i]!=sub[k]) k=next[k-1]; 13 if(sub[i]==sub[k]) k++; 14 next[i]=k; 15 } 16 } 17 void kmpMatch(){ 18 int lt=strlen(str); 19 int lb=strlen(sub); 20 for(int i=0,q=0; i<lt; i++){ 21 while(q>0 && sub[q]!=str[i]) q=next[q-1]; 22 if(sub[q]==str[i]) q++; 23 if(q==lb){ 24 ok=1; 25 break; 26 } 27 } 28 } 29 int main(){ 30 while(gets(str)!=NULL){ 31 gets(sub); 32 ok=0; 33 int lt=strlen(str); 34 int lb=strlen(sub); 35 if(lt<lb){ 36 printf("no\n"); 37 continue; 38 } 39 for(int i=0; i<lt; i++) str[i+lt]=str[i]; 40 str[2*lt]=‘\0‘; 41 // if(strstr(str,sub)!=NULL) printf("yes\n");直接用strstr() 42 // else printf("no\n"); 43 kmpMatch(); 44 printf("%s\n",ok?"yes":"no"); 45 } 46 return 0; 47 }
HDU 2203 亲和串(KMP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。