(字符串的模式匹配4.7.18)POJ 2406 Power Strings(求一个字符串的最小重复串)
注意,在IDE运行时,可能会因为开的数组太大而报错,这时我们可以把数组开小一点来进行调试....提交的时候把数组的大小改成1000005即可。。。。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 1000005;int main() {char str[maxn];while (scanf("%s", str) != EOF) {if (str[0] == '.') {break;}int len = strlen(str);int suffix[maxn + 1];//应用KMP算法计算单词w的前缀函数suffix[0] = -1;suffix[1] = 0;int cur, p = 0;for (cur = 2; cur <= len; ++cur) {//这里的len不要写成strlen(str),这样可能会导致超时while (p >= 0 && str[p] != str[cur - 1]) {p = suffix[p];}suffix[cur] = ++p;} //如果len是(len - suffix[len])的前缀,即,假如当前的重复串的长度能被原串的长度整除...if((len % (len - suffix[len])) == 0){printf("%d\n", (len / (len - suffix[len])));}else{printf("1\n");}}return 0;}