杭电1867

KMP的简单应用

注意前后缀都可以，还有就是都不匹配就按字典序输出；

 #include <iostream>
 #include<stdio.h>
 #include<string.h>
 #include<string>
 using namespace std;
 int next[100010];
 void getNext(char P[])
 {
    int j=0,k=-1;
    next[0]=-1;
    int lenP=strlen(P);
    while(j<lenP)
    {
        if(k==-1 || P[j]==P[k])
        {
            k++;j++;
            next[j]=k;
        }
        else
            k=next[k];
    }
 }
 int KMP(char T[],char P[])
 {
     memset(next,0,sizeof(next));
     getNext(P);
     int posP=0,posT=0;
     int lenT=strlen(T);
     while(posT<lenT)
     {
         if(posP==-1 || P[posP]==T[posT])
         {
             posP++;posT++;
         }
         else
             posP=next[posP];
     }
     return posP;
 }
 char S1[100005],S2[100005];
 int main()
 {
     while(scanf("%s %s",S1,S2)!=EOF)
     {
        int len1=KMP(S1,S2);
        int len2=KMP(S2,S1);
        if(len1==len2)
        {
            if(strcmp(S1,S2)<0)
            {
                printf("%s%sn",S1,S2+len1);
            }
            else
            {
                printf("%s%sn",S2,S1+len1);
            }
        }
        else
        if(len1<len2)
        {
            printf("%s%sn",S2,S1+len2);
        }
        else
           printf("%s%sn",S1,S2+len1);
     }
     return 0;
 }

最后

以上就是虚心诺言为你收集整理的杭电1867的全部内容，希望文章能够帮你解决杭电1867所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。