Jisoo

找一个最长的周期

就是要找最短的border然后加上中间的部分

这样 $kmp$出动

然后发现可以 “记忆化”一波进行优化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define int long long 
using namespace std;
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1; 
    //  cout<<isdigit(c)<<" "<<c<<" "; 
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar(); 
    } 
    now*=f; 
}
int n;
int ne[1000005];
string s;
int ans;
signed main(){
    read(n);
    cin>>s;
    s=' '+s;
    int f=0;
    for(int i=2;i<=n;++i){
        while(f&&s[f+1]!=s[i]) f=ne[f];
        if(s[f+1]==s[i]) f++;
        ne[i]=f;
    }
    for(int i=2;i<=n;++i){
        int j=i;
        while(ne[j]) j=ne[j];
        if(ne[i]) ne[i]=j;
        ans+=(i-j); 
    }
    cout<<ans;
    return 0;
}