题意：求一个字符串的所有前缀是否是复制出来的。
解题思路：next 数值判断即可
解题代码：
1 // File Name: getnext.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月09日 星期二 22时35分02秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 char str[1000004]; 28 int next[1000005]; 29 void getnext() 30 { 31 int len = strlen(str); 32 next[0] = -1; 33 int k = -1; 34 int j = 0 ; 35 int sum = 0 ; 36 while(j <= len - 1) 37 { 38 if(k == -1 || str[j] == str[k]) 39 { 40 ++j; 41 ++k; 42 next[j] = k ; 43 } 44 else { 45 k = next[k]; 46 } 47 } 48 /* for(int i = 0 ;i <= len; i ++) 49 printf("%d ",next[i]); 50 printf(" ");*/ 51 for(int i = 2;i <=len; i ++) 52 { 53 int t = (i - next[i]); 54 if(i % t == 0 && i /t != 1) 55 { 56 printf("%d %d ",i,i/t); 57 } 58 } 59 60 } 61 int main(){ 62 int n ; 63 int t = 0 ; 64 while(scanf("%d",&n) != EOF,n) 65 { 66 t++ ; 67 scanf("%s",str); 68 printf("Test case #%d ",t); 69 getnext(); 70 printf(" "); 71 } 72 return 0; 73 }