【最短循环节问题——hash】

题目

• 最短的循环节长度就等于 自身长度 - 最长的头尾缀匹配长度（不考虑字符串自身和自身匹配）
• 如果不存在匹配，则最短循环节为自身，长度为 自身长度

代码

#include <iostream>
using namespace std;
using ll = long long;const int mod = 1e9+7;
const int base = 233;
const int N = 1e6+10;ll f[N], pq[N];
int n;
string s;void init_hash(string s)
{pq[0] = 1;f[0] = s[0] % mod;for(int i = 1; i < n; i++){pq[i] = pq[i-1] * base % mod;f[i] = f[i-1] * base % mod + s[i];f[i] %= mod;}
}
ll get_hash(int l, int r)
{if(l == 0) return f[r];return (f[r] - f[l-1] * pq[r-l+1] % mod + mod) % mod;
}
int main()
{cin >> n;cin >> s;init_hash(s);int ans = -1;for(int i = 0; i < n-1; i++){if(get_hash(0, i) == get_hash(n-i-1, n-1))ans = n - (i+1);}if(ans == -1) ans = n;cout << ans;return 0;
}