Description
给你一个字符串，它是由某个字符串不断自我连接形成的。 但是这个字符串是不确定的，现在只想知道它的最短长度是多少.
Input
第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串，全由小写字母组成.
Output
输出最短的长度
Sample Input
8 cabcabca
Sample Output
3
所求即是最小循环节！输出n - nxt[n]!
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int SZ = 1000010; char s[SZ]; int len, nxt[SZ]; void get(char s[]) { nxt[1] = 0; for(int i = 2; i <= len; i++) { int p = nxt[i - 1]; while(p && s[i] != s[p + 1]) p = nxt[p]; if(s[p + 1] == s[i]) p ++; nxt[i] = p; } } int main() { scanf("%d", &len); scanf("%s", s + 1); get(s); printf("%d", len - nxt[len]); return 0; }转载于:https://www.cnblogs.com/Loi-Vampire/p/6017053.html
相关资源：JAVA上百实例源码以及开源项目