首页 > > 程序设计 > C/C++ >

Seek the Name, Seek the Fame POJ - 2752

2018-06-17 21:54:27来源：未知阅读 ()

http://972169909-qq-com.iteye.com/blog/1071548

（kmp的next的简单应用）

简单来讲，这道题就是要找字符串的所有相同前缀后缀。

第一次找出最大的相同前缀后缀，然后找次大的。次大的相同前缀后缀的前缀一定是在最大相同前缀后缀的前缀的前面取一段，次大的相同前缀后缀的后缀一定是在最大相同前缀后缀的后缀的后面取一段。由于是相同前缀后缀，将后缀的后面取的那一段移到前缀后面去取，问题就变为也就是从最大相同前缀后缀的前缀中取出其最大相同前缀后缀。这个过程是递归的，直到最大相同前缀后缀的长度为0。

当然，kmp的next中不会留下整个字符串长度m的痕迹，因此m要单独输出。

 1 #include<cstdio>
 2 #include<cstring>
 3 char s[1001000];
 4 int f[1001000];
 5 int m;
 6 int getf()
 7 {
 8     int i=0,j=f[0]=-1;
 9     while(i<m)
10     {
11         while(j>=0&&s[i]!=s[j])
12         {
13             j=f[j];
14         }
15         i++;j++;
16         f[i]=j;
17     }
18 }
19 void print(int i)
20 {
21     if(f[i]>0)    print(f[i]),printf("%d ",f[i]);
22 }
23 int main()
24 {
25     while(scanf("%s",s)==1)
26     {
27         m=strlen(s);
28         getf();
29         print(m);
30         printf("%d\n",m);
31     }
32     return 0;
33 }