POJ Power Strings(KMP)

本文主要是介绍POJ Power Strings(KMP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://poj.org/problem?id=2406

KMP求最小循环节个数。最小循环节= n - next[n];

代码：

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
const int N = 1000005;char s[N];
int next[N], n;void get_next(char *seq, int m) {next[0] = -1;int j = next[0];for (int i = 1; i < m; i++) {while (j >= 0 && seq[i] != seq[j + 1]) j = next[j];if (seq[i] == seq[j + 1]) j++;next[i] = j;}
}bool kmp(char *seq, char *seq1, int n, int m) {int j = next[0], ans = 0;for (int i = 0; i < n; i++) {while (j >= 0 && seq[i] != seq1[j + 1]) j = next[j];if (seq[i] == seq1[j + 1]) j++;if (j == m - 1) {//根据题意}}return false;
}int solve() {if (n - (next[n - 1] + 1) == 0) return 1;if (n % (n - (next[n - 1] + 1)) == 0) return n / (n - (next[n - 1] + 1));else return 1;
}int main() {while (~scanf("%s", s) && strcmp(s, ".") != 0) {n = strlen(s);get_next(s, n);printf("%d\n", solve());}return 0;
}

这篇关于POJ Power Strings(KMP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---