HDU-2594 Simpsons’ Hidden Talents (kmp)

题意：给出两个字符串a,b然后 a前缀与b后缀的最长公共部分 并输出 长度。

思路：我们知道next[]数组就是求 某个字符串的最长公共前后缀的，所以就会想到把a,b两个串相连 ，然后再来整体求next[]数组 .当然还要注意下 得到的 长度不能超过 a,b 串本身.

其他：关于字符串输入的问题，加了cin加速还是 TLE 了.....没办法只能换scanf

AC代码：

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 5e4+9;
int nex[maxn<<1];
int len1,len2;
int len;
char s1[maxn<<1],s2[maxn];
void getnext(){
    int i=0,j=-1;
    nex[i] = j;
    while(i<len){
        if(j==-1||s1[i]==s1[j]){
            nex[++i] = ++j;
        }else j = nex[j];
    }
}
int main(){ 
    while((~scanf("%s%s",s1,s2))){
          len1=strlen(s1);
        len2=strlen(s2);
        len = len1+len2;
        strcat(s1,s2);
        getnext();
        while(nex[len]>len1 || nex[len]>len2)//next不能比len1或len2大 
            len=nex[len];//所以把长度限制在len1或len2以内 
        if(nex[len]){
            for(int i=0;i<nex[len];i++)
                printf("%c",s1[i]);
            printf(" %d\n",nex[len]);
        }else printf("0\n");
    }    
}

 

TLE代码：

#include <iostream>
using namespace std;
const int maxn = 5e4+9;
int nex[maxn<<1];
int len,len1,len2;
string s1,s2;
void getnex(){
    int i=0,j=-1;
    nex[i] = j;
    while(i<len){
        if(j==-1||s1[i]==s1[j]){
            nex[++i] = ++j;
        }else j = nex[j];
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); 
    while(cin>>s1>>s2){
        len1 = s1.size();
　　　　　len2 = s2.size();
　　　　　s1 += s2;
        len = s1.size();
        getnex();
　　　　　while(nex[len]>len1 || nex[len]>len2)//next不能比len1或len2大 
            len=nex[len];//所以把长度限制在len1或len2以内 
        if(nex[len]){
            for(int i=0;i<nex[len];i++)
                printf("%c",s1[i]);
            printf(" %d",nex[len]);
        }else printf("0\n");
    }    
}