KMP 最小循环节

传送门

考察KMP的最小循环节知识点，相关证明可在该链接下查阅。
循环节传送门

对于这道题，和常规思路一样先求出next数组，然后进行匹配，在求循环节的过程中要取最大值。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
char s[N], t[N];
int ne[N];
int main(){
	int n;
	cin >> n;
	cin >> s + 1;
	for(int i = 2, j = 0; i <= n; i ++){
		while(j && s[i] != s[j + 1])
			j = ne[j];
		if(s[i] == s[j + 1])
			j ++;
		ne[i] = j;
	}
	int maxn = -1;
	for(int i = n; i >= 1; i --){
		if(i % (i - ne[i]) == 0){
			maxn = max(maxn, i - ne[i]);
		}
	}
	cout << maxn << endl;
	
	return 0;
}