题目来源：POJ2406
题目描述： 1457：Power Strings 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 502 通过数: 195 【题目描述】 原题来自：POJ 2406 给定若干个长度 ≤106 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：ababab 则最多有 3 个 ab 连接而成。
【输入】 输入若干行，每行有一个字符串，字符串仅含英语字母。特别的，字符串可能为 . 即一个半角句号，此时输入结束。 【输出】 【输入样例】 abcd aaaa ababab . 【输出样例】 1 4 3
思路：KMP算法，检查字符串I+1位是否与j+1位匹配，若不匹配，则回到p[j]（表示之前一位与i匹配的位置，可以说这里pj对应下标的字符与j对饮下标字符相同），再判断下一位是否相同。最后一次循环子串是n-p[n]到n，则一共循环n/(n-p[n])次.下面给出AC代码：
#include<bits/stdc++.h> using namespace std; const int N=1e6+5; char a[N]; int p[N],n; void kmp() { p[1]=0;int j=0; for(int i=1;i<n;i++) { while(j>0&&a[j+1]!=a[i+1])j=p[j]; if(a[j+1]==a[i+1])j++;//如果已经相等，则看接下来的字符相不相等，若不相等则返回，说明还没有开始重复；否则接着匹配 p[i+1]=j;//开始时不相等，那么j不自增，继续看之后的串哪个i开始与j匹配 } } int main() { while(1) { scanf("%s",a+1); if(a[1]=='.')break; n=strlen(a+1); kmp(); if(n%(n-p[n])==0) printf("%d\n",n/(n-p[n])); else printf("%d\n",1); } return 0; }