hdu2594Simpsons’ Hidden Talents（KMP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2594

将两个串连接，中间用'#'连接，进行KMP。

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=100010;
 4 int n,m;
 5 char s[maxn];
 6 int nex[maxn];
 7 
 8 int main()
 9 {
10     while(scanf("%s",s)!=EOF)
11     {
12         n=strlen(s);
13         s[n]='#';   //防止KMP时两个串真正连接
14         scanf("%s",s+n+1);
15         getchar();
16         m=strlen(s);
17         int i=0,j=-1;
18         nex[0]=-1;
19         while(i<m)
20         {
21             if(j==-1||s[i]==s[j])
22                 nex[++i]=++j;
23             else j=nex[j];
24         }
25         s[nex[m]]='';
26         if(nex[m]) printf("%s %d
",s,nex[m]);
27         else printf("0
");
28     }
29 }