HDU-2203 亲和串 KMP

亲和串

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

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

　　该题要求一个串循环后是否包含另外一个串，其实只要将母串重复一次再进行KMP匹配就行了，因为在重复母串的过程中，其实据已经将循环后的所有可能都列举出来了，比如串 "ABCD" 重复后为 "ABCDABCD" 在这个串中 "BCDA" , "CDAB" 以及 "DABC" 都相继出现了。用该种方法求解的过程中还应注意当子串长度超过母串时不进行匹配，因为那样可能输出错误的判断，比如上例中子串为 "ABCDA" 那么也会输出 yes 了。

　　代码如下：

#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

char s1[200010], s2[100005], temp[100005];

int next[100005];

void getnext(  )
{
int k = 1, j = 0, len = strlen( s2 + 1 );
while( k < len )
    {
if( j == 0 || s2[k] == s2[j] )
        {
++j, ++k;
if( s2[j] == s2[k] )
            {
                next[k] = next[j];
            }
else
                next[k] = j;
        }
else
            j = next[j];
    }
}

bool kmp(  )
{
int k = 0, j = 0, len1= strlen( s1 + 1 ), len2 = strlen( s2 + 1 );
while( k <= len1 && j <= len2 )
    {
if( j == 0 || s1[k] == s2[j] )
        {
++j, ++k;
        }
else
        {
            j = next[j];
        }
    }
if( j > len2 )
return true;
else
return false;
}

int main()
{
while( scanf( "%s %s", s1 + 1, s2 + 1 ) != EOF )
    { 
int len1 = strlen( s1 + 1 ), len2 = strlen( s2 + 1 );
if( len2 > len1 )
        {
            puts( "no" );
continue;
        }
        strcpy( temp, s1 + 1 );
        strcat( s1 + 1, temp );
        getnext();
        printf( kmp() ? "yes\n" : "no\n" );
    }
}