hdu 2203 --亲和串

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跑一遍就好。

ac代码：

#include<stdio.h>  
#include<string.h>  
#include<cstring>  
#define val 100005  
int lens,lenp,next[val];  
char s[val*2],p[val];  
bool kmp();  
int main()  
{  
    while(scanf("%s",s)!=EOF)  
    {  
        scanf("%s",&p);  
        lens=strlen(s);  
        lenp=strlen(p);  
        strncpy(s+lens,s,lens);  
        lens*=2;  
        if(kmp()) printf("yes
");  
        else printf("no
");  
    }  
    return 0;  
}  
bool kmp()  
{  
    void set_next();  
    int i,j;  
    i=j=0;  
    set_next();  
    while(i<lens&&j<lenp)  
    {  
        if(j==-1||s[i]==p[j])  
        {  
            i++;  
            j++;  
        }  
        else j=next[j];  
    }  
    if(j<lenp) return false;  
    else return true;  
}  
void set_next()  
{  
    int j,k;  
    j=0,k=-1;  
    next[j]=k;  
    while(j<lenp)  
    {  
        if(k==-1||p[j]==p[k])  //当跳转后的指向-1 或者自匹配相同的时候 向后挪位
        {  
            k++;  
            j++;  
            next[j]=k;  
        }  
        else k=next[k];  //失配的时候 跳转到能够取的位置
    }  
}

hdu 2203 --亲和串

相关推荐