hdu 2594 Simpsons’ Hidden Talents

 1 #include<cstdio>  
 2 #include<iostream>  
 3 #include<algorithm>
 4 #include<math.h> 
 5 #include<string.h>  
 6 #include<vector> 
 7 #include<queue>
 8 #include<iterator>
 9 #include<vector>
10 #include<set>
11 #define dinf 0x3f3f3f3f
12 typedef long long ll;
13 //const int Max=(1<<16)+10;
14 using namespace std;
15   
16 const int MAX=50000+10;  
17 char s1[MAX*2],s2[MAX];  
18 int Next[MAX*2];  
19   
20 void get_next(char *a){  
21     int i=-1,j=0,len=strlen(a);  
22     Next[0]=-1;  
23     while(j<len){  
24         if(i == -1 || a[i] == a[j])Next[++j]=++i;  
25         else i=Next[i];  
26     }  
27     return;  
28 }  
29   
30 int main(){  
31     while(cin>>s1>>s2){  
32         int lena=strlen(s1),lenb=strlen(s2),len=lena+lenb;  
33         strcat(s1,s2);  
34         get_next(s1);  
35         while(Next[len]>lena || Next[len]>lenb)len=Next[len];  
36         len=Next[len];  
37         for(int i=0;i<len;++i)cout<<s1[i];  
38         if(len)cout<<‘ ‘;  
39         cout<<len<<endl;   
40     }  
41     return 0;  
42 }