题面

标准kmp

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 char a[1000010];
 8 int n,fail[1000010];
 9 
10 int main(){
11     scanf("%d",&n);
12     scanf("%s",a);
13     int i,j;
14     long long cnt=0;
15     fail[0]=fail[1]=0;j=0;
16 
17      for(i=1;i<n;i++)
18     {
19 
20         while(j&&(a[i]!=a[j])) 
21         j=fail[j];
22 
23         j+=(a[i]==a[j]);
24         fail[i+1]=j;
25     }
26 
27     for(i=1;i<=n;i++)
28     {
29         j=i;
30 
31         while(fail[j]) 
32         j=fail[j];
33 
34         if(fail[i]!=0) 
35         fail[i]=j;
36 
37         cnt+=i-j;
38     }
39     printf("%lld",cnt);
40 }