poj 2406 KMP算法中next的一个性质
问题是：如何快速找出S的最小循环周期（循环节）呢？
Len是s的长度
给出结论：如果len%(len-next[len-1])==0,则字符串中必存在最小循环节，且循环次数即为 len/(len-next[len-1])
所以这题知道了上述结论，写出NEXT即可求得循环周期。
#include <iostream>#include <string.h>using namespace std; char b[1000000]; int next[1000000]; //数组一开始没开大，runtime error了...- -、int main(){ int temp,i; while (cin>>b) { if (b[0]=='.') break; int len=strlen(b); memset(next, 0, sizeof(next)); for (i = 1; i < len; i++) { temp = next[i - 1]; while (temp && b[temp] != b[i]) temp = next[temp - 1]; if (b[temp] == b[i]) next[i] = temp + 1; else next[i] = 0; } if (len%(len-next[len-1])==0) cout<<len/(len-next[len-1])<<endl; else cout<<1<<endl; } return 0;}