(字符串的模式匹配4.7.18)POJ 1961 Period(求一个串到第i个字符循环节出现的次数)
/* * POJ_1961.cpp * * Created on: 2013年10月29日 * Author: Administrator */#include <iostream>#include <cstdio>#include <cstring>const int maxn = 1000005;//在IDE测试时可能会报错,因为可能它开不了那么大的数组,这是需要把maxn调小一点来进行测试int main() {int n;int counter = 1;while (scanf("%d", &n) != EOF, n) {char str[maxn];scanf("%s", str);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) {while (p >= 0 && str[p] != str[cur - 1]) {p = suffix[p];}suffix[cur] = ++p;}if(counter != 1){printf("\n");}printf("Test case #%d\n",counter++);int i;/** * POJ_2406 :其实求的是整个串的循环节数,而 * POJ_1961 :求的是一个串到第i个字符时所出现的循环节数...也就是多了一个循环而已 * */for (i = 1; i <= n; ++i) {//如果len是(len - suffix[len])的前缀,即,假如当前的重复串的长度能被原串的长度整除...if ((i % (i - suffix[i])) == 0 &&(i / (i - suffix[i])>1)) {printf("%d %d\n", i ,(i / (i - suffix[i])));}}}return 0;}