记一个KMP算法的应用，经典的KMP算法详解还是看
问题：给一个串，求这个串前i位构成的前缀由多少个子串组成。
比如aabaabaabaab，前2位是aa，a重复了2次，前6位是aabaab，aab重复了2次，前9位是aabaabaab，aab重复了3次，前12位是aabaabaabaab，aab重复了4次。
先说一下next()函数。pre[i] = j表示 S[1...j] = S[i - j....i];
下面讨论当i % (i - pre[i]) == 0 时，例如i = 12, pre[12] = 9：
如图。
S[1...9] == S[3...12];
因为已知 i % (i - pre[i]) == 0; 那么把i分成 i / (i - pre[i])段。
已知：
s3 == t3;
s2 == t2;
s1 == t1;
又因为t3 == s2, t1 == s1。所以 t1 = t2 = t3 = s1 = s2 = s3，也就是说 i / (i - pre[i])这几段中每一段都相等。
现在回到原问题：求这个串前i位构成的前缀由多少个子串组成，只需要找到i / (i - pre[i]) == 0的点i，则共有 i / (i - pre[i])个相同的子串构成前缀S[1...i]。
练习：，
附1961的代码：
#include#include #include #include #include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define REP(i, n) for(i = 0; i < n; ++i)#define FOR(i, l, h) for(i = l; i <= h; ++i)#define FORD(i, h, l) for(i = h; i >= l; --i)#define L(x) x << 1#define R(x) x << 1 | 1#define MID(l, r) (l + r) >> 1typedef long long LL;using namespace std;const int N = 1000010;char s[N];int pre[N];int dp[N]; //这里加了一个数组，记录到i位置时所构成的前缀由多少个子串组成。int n;void Next() { int i, j = -1; pre[0] = -1; for(i = 1; i < n; ++i) { while(j > -1 && s[j+1] != s[i]) j = pre[j]; if(s[j+1] == s[i]) ++j; pre[i] = j; }}int main() { freopen("data.in", "r", stdin); int i, cas = 0; while(scanf("%d", &n), n) { scanf("%s", s); printf("Test case #%d\n", ++cas); Next(); REP(i, n + 1) dp[i] = 1; FOR(i, 1, n - 1) { if((i + 1) % (i - pre[i]) == 0 && pre[i] != -1) { dp[i] = dp[pre[i]] + 1; //到i的前缀就等于到pre[i]的前缀子串数加上 [pre[i], i]这个子串。 printf("%d %d\n", i + 1, dp[i]); //其实直接输出(i + 1)/(i - pre[i])就行，这里写搓了。。。T_T } } cout << endl; } return 0;}