【HDU 2203】亲和串

题

题意

给你一个字符串s1，字符串s2，s1循环移位，使s2包含在s1中，则s2 是s1的亲和串

分析

把s1自身复制一遍接在后面。

方法一: 用strstr函数。

方法二: KMP算法。

方法三: 用C++的string的find函数。

代码

方法一:

#include<cstdio>

#include<cstring>

char s1[],s2[];

int len;

int main()

{

    while(~scanf("%s",&s1))

    {

        len=strlen(s1);

        for(int i=; i<len; i++)

            s1[len+i]=s1[i];

        scanf("%s",&s2);

        if(strstr(s1,s2)-s1>=) printf("yes\n");

        else printf("no\n");

        memset(s1,,sizeof(s1));

        memset(s2,,sizeof(s2));

    }

    return ;

}

方法二：

#include<cstdio>

#include<cstring>

char S[],T[];

int next[],len;

void getNext(){

    int i,k=-;

    next[]=k;

    for(i=;T[i];i++){

        while(k>= && T[i]!=T[k+]) k=next[k];

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

        next[i]=k;

    }

}

int KMP(){

    int i=,j=;

    while(i==-||S[j]&&T[i]){

        if(i==-||S[j]==T[i]){

            i++;

            j++;

        }else

            i=next[i];

    }

    if(!T[i])

        return j-i+;

    return -;

}

int main()

{

    while(~scanf("%s",S))

    {

        len=strlen(S);

        for(int i=len;i<*len;i++)

            S[i]=S[i-len];

        scanf("%s",T);

        getNext();

        if(KMP()<) printf("no\n");

        else printf("yes\n");

        memset(S,,sizeof(S));

        memset(T,,sizeof(T));

    }

    return ;

}

方法三

#include<iostream>

using namespace std;

int main()

{

    string P,T;

    while(cin>>P>>T)

    {

        P+=P;

        if(P.find(T)!=string::npos)cout<<"yes"<<endl;

        else cout<<"no"<<endl;

    }

    return ;

}

巴特西

【HDU 2203】亲和串

题意

分析

代码

方法一:

方法二：

方法三

最新文章

热门文章