题意:判断一个字符串是由几个子串重复连接而成.
思路:字符串的自身匹配,考虑用KMP的next函数.
假设数组下标从0开始,Next[i]数组的值k表示B数组1<=j<=i上右端 与 自身0<=j左端匹配的最大长度(注意不包含0号位置,因为next数组使用时j是要减小的!).
那么考虑,对于一个power string来说,next[len-1]就是len-1-[重复串长].非power string的next[len-1]就不满足.也就是把重复串长提取出来的话,不能整除总长.那么n=1.
想出这个公式就基本过了..
#include <cstdio> #include <cstring> //5068K 110MS using namespace std; const int MAXW = 1000005; char B[MAXW]; int next[MAXW]; void prekmp() { int j = -1; next[0] = -1; for(int i=1; B[i]; i++) { while(j != -1 && B[j+1] != B[i]) j = next[j]; if(B[i] == B[j+1]) j++; next[i] = j; } } int main() { while(1) { scanf("%s",B); if(B[0]=='.') break; int len = strlen(B); prekmp(); int t= len - (next[len-1] + 1); if(!(len%t)) printf("%d\n",len/t); else printf("1\n"); } }