注意: 由于题目说只要 A 满足是 2Q 的前缀, 所以求的不是严格的最大循环子串 (20pts)
我们需要求出的是在主串中最小的, 既是前缀又是后缀的子串
利用 f 数组的性质: 前缀 i 的长度为 next[i] 的前缀和后缀是相等的 (然而我之前并不知道 qwq)
- (对拍 10 分钟不如手写小数据 (大雾))
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- char a[1000003];
- int n,f[1000003];
- long long ans;
- int main(){
- scanf("%d",&n); scanf("%s",a);
- int j;
- for(int i=1;i<n;++i){
- j=f[i];
- while(j&&a[i]!=a[j]) j=f[j];
- f[i+1]= a[i]==a[j] ? j+1:0;
- }
- for(int i=1;i<=n;++i){
- if(!f[i]) continue;
- j=f[i];
- while(f[j]) f[i]=j=f[j];
- ans+=i-j;
- }
- /*for(int i=1;i<=n;++i){
- if(!f[i]) continue;
- int len=i-f[i];
- ans+=i-(i%len ? i%len:len);
- } // 并不能用在这题上
- // 8 uuauuauu 反例
- // 24*/
- printf("%lld",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2760536.html