传送门：点击打开链接
题意：已知原串，在首或者尾加上一些字符后，变成至少有一个循环节循环2次变成新串
思路：我们能很容易的发现，在首添加字母和在尾添加字母效果是一样的，所以我们只考虑在末尾添加
首先我们都知道，KMP可以用来求前缀中的最长循环节长度。知道了这个有什么用呢？
我们枚举所有的前缀，然后取得循环节的长度w，与此时后面剩下的字符串的长度t去比较
如果后面剩下的字符串等于原字符串的前缀，那么就更新一次答案w-t取最小
利用hash记录前缀和后缀，能快速完成后面那一步
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout << "[" << x << "]"
#define FIN freopen("input.txt", "r", stdin)
#define FOUT freopen("output.txt", "w+", stdout)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;const int MX = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int se = 131;char S[MX];
int Next[MX];
void GetNext(char S[], int n) {Next[0] = 0;for(int i = 1; i < n; i++) {int j = Next[i - 1];while(j && S[i] != S[j]) j = Next[j - 1];Next[i] = S[i] == S[j] ? j + 1 : 0;}
}
int f(int p) {return (p + 1) % (p - Next[p] + 1) == 0 ? p - Next[p] + 1 : p + 1;
}ULL L[MX], R[MX];
int main() {int T; //FIN;scanf("%d", &T);while(T--) {scanf("%s", S);int n = strlen(S);GetNext(S, n);L[0] = 0;for(int i = 0; i < n; i++) {L[i + 1] = L[i] * se + S[i];}R[n] = 0; ULL fac = 1;for(int i = n - 1; i >= 0; i--) {R[i] = R[i + 1] + fac * S[i];fac *= se;}int ans = INF;for(int i = 0; i < n; i++) {int w = f(i), res = n - i - 1;if(w < res) continue;if(R[n - res] == L[res]) {ans = min(ans, w - res);}}printf("%d\n", ans);}return 0;
}