亲和串

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的亲和串。

Input

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

Output

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

Sample Input

AABCD

CDAA

ASD

ASDF

Sample Output

yes

思路：

先算出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。

代码：

 #include <cstdio>

 #include <cstring>

 const int N=;

 char str[*N];

 char sub[N];

 int next[N];

 int ok;

 void makeNext(){

     int l=strlen(sub);

     next[]=;

     for(int i=,k=; i<l; i++){

         while(k> && sub[i]!=sub[k])    k=next[k-];

         if(sub[i]==sub[k])  k++;

         next[i]=k;

     }

 }

 void kmpMatch(){

     int lt=strlen(str);

     int lb=strlen(sub);

     for(int i=,q=; i<lt; i++){

         while(q> && sub[q]!=str[i])    q=next[q-];

         if(sub[q]==str[i])  q++;

         if(q==lb){

             ok=;

             break;

         }

     }

 }

 int main(){

     while(gets(str)!=NULL){

         gets(sub);

         ok=;

         int lt=strlen(str);

         int lb=strlen(sub);

         if(lt<lb){

             printf("no\n");

             continue;

         }

         for(int i=; i<lt; i++)  str[i+lt]=str[i];

         str[*lt]='\0';

    //     if(strstr(str,sub)!=NULL)   printf("yes\n");直接用strstr()

    //     else printf("no\n");

         kmpMatch();

         printf("%s\n",ok?"yes":"no");

     }

     return ;

 }

秒客网

HDU 2203 亲和串(KMP)

亲和串

相关文章