题目链接:http://poj.org/problem?id=2406
题意:就是求一个字符串最多有几个相同的小字符串组成。
题解:直接求一下next然后找到长度,长度就是len-1-next[len-1]。
#include <iostream> #include <cstring> using namespace std; const int M = 1e6 + 10; char s[M] , p[M]; int Next[M]; void getnext() { int len = strlen(s); Next[0] = -1; int i = 0 , j = -1; while(i < len) { while(j != -1 && s[i] != s[j]) j = Next[j]; Next[++i] = ++j; } } int main() { while(scanf("%s" , s)) { if(s[0] == '.') break; getnext(); int len = strlen(s); int L = len - Next[len - 1] - 1; if(L == 0 || len % L != 0) { printf("1 "); } else { int flag = 0 , count = 0; if(len % L == 0) { for(int i = len - L ; i < len ; i++) { p[count++] = s[i]; } //cout << p << endl; int num = 0; for(int i = 0 ; i < len ; i++) { if(p[num++] != s[i]) { flag = 1; break; } if(num == count) { num = 0; } } if(flag) { printf("1 "); } else { printf("%d " , len / L); } } else { printf("1 "); } } } return 0; }