还是KMP，我觉得应该把自己的心得写一下。这题要求的是“前后辍”，即既是前辍又是后辍，比如“abcab”中的“ab”。KMP求next数组有两种算法，一种是：

if(t[i] == t[j])

{　i++; j++; next[i] = j; }

另一种是：

if(t[i] == t[j])

{　i++; j++;

　　if(t[i] != t[j])

　　　　next[i] = j;

　　else

　　　　next[i] = next[j];

}

第二种是第一种的改进版，不过这一题恰恰是第一种比较合适。对字串“ababcabab”来说，两种方法构造的next分另为：

a	b	a	b	c	a	b	a	b
-1	0	-1	0	2	-1	0	-1	0	4
-1	0	0	1	2	0	1	2	3	4

 

 

 

 

 

在文中插表格太麻烦，我就做成这样了。上一行是第二种，下一行是第一种方法，从左到右分别为next[0]到next[10]，第一种方法的数组满足这样的性质：对任意 i ,next[i] = j 表示字串中前 i 个字符组成的子串的最长“前后辍”长度为 j 。比如，‘c’ 对应着next[4] = 2，那么前4个字符“abab” 的最长前后辍“ab”的长度为2。这样就好办多了，“ababcabab” 的最长串为“abab”，“abab”的最长串为“ab”，递归打印就行了。

1 #include 
     
       2 #include 
      
        3 int next[1000005],len; 4 char T[1000005]; 5 void getnext(char *t) 6 { 7     int i=0,j=-1; 8     len = strlen(T); 9     next[0] = -1;10     while(i < len)11         if(j == -1 || T[i]==T[j])12         {13             i++;j++;14             next[i] = j;15         }16         else j = next[j];17 }18 void show(int a)19 {20     if(next[a])21         show(next[a]),22         printf(" %d",a);23     else printf("%d",a);24 }25 int main()26 {27     while(~scanf("%s",T))28     {29         getnext(T);30         show(len);31         printf("\n");32     }33     return 0;34 }
      
     

 

PS：刚刚才发现，第二种数组虽不对任意 i 满足上述性质，但是在这一题相应的位置上是满足的，晕死，那不就是两种都可以了。