求字符串中循环子串的长度 ← KMP算法

【题目来源】
改编自：https://www.luogu.com.cn/problem/P4391

【问题描述】
给你一个字符串 s1​，它是由某个字符串 s2​ 不断自我连接形成的。但是字符串 s2​ 是不确定的，现在只想知道它的最短长度是多少。

【输入格式】
仅一行，表示输入字符串 s1​ 的一个子串。

【输出格式】
仅一行，表示 s2​ 的最短长度。

【说明/提示】
样例cabcabca的解释：对于样例，我们可以利用abc不断自我连接得到abcabcabc，读入的cabcabca是它的子串。

【规模与约定】
对于全部的测试点，保证字符串的长度 ≤10^6 。

【算法分析】
首先要注意，本题输入的字符串比较特殊，是由某个字符串不断自我连接构成的某个字符串的子串。在这个基础上，绘制样例 cabcabca 的前缀表及next数组如下文示意图所示。
由 https://blog.csdn.net/hnjzsyjyj/article/details/127171330 知，前缀表与next数组虽然是有关系的，但是它们不是一回事。且next数组可通过“将前缀表每一位都向右移动1位（最右位舍去）并在最左位补一个-1”得到。
观察示意图可知，循环子串的长度为：T.length()-ne[T.length()]

 
【算法代码】

#include<iostream>
using namespace std;
 
const int maxn=100;
int ne[maxn];
 
void getNext(string T) {
	int len=T.length();
	int i=0, j=-1;
	ne[0]=-1;
	while(i<len) {
		if(j==-1 || T[i]==T[j]) {
			ne[++i]=++j;
		} else j=ne[j];
	}
}
 
int main() {
	string T;
	getline(cin,T);
	getNext(T);
	cout<<(T.length()-ne[T.length()]);
 
	return 0;
}
 
 
/*
in1: cabcabca
out1: 3

in2: ac@# ac@# ac@# 
out2: 5
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/127112363
https://blog.csdn.net/hnjzsyjyj/article/details/127086502
https://blog.csdn.net/hnjzsyjyj/article/details/127105603
https://www.luogu.com.cn/problem/solution/P4391
https://www.luogu.com.cn/problem/P4391
https://blog.csdn.net/hnjzsyjyj/article/details/120330090