題目描述

一個(gè)串是有限個(gè)小寫字符的序列,特別的,一個(gè)空序列也可以是一個(gè)串. 一個(gè)串PP是串AA的前綴, 當(dāng)且僅當(dāng)存在串BB, 使得A=PBA=PB. 如果 P!=AP!=A 并且PP不是一個(gè)空串,那么我們說PP是AA的一個(gè)properproper前綴. 定義QQ 是AA的周期, 當(dāng)且僅當(dāng)QQ是AA的一個(gè)properproper 前綴并且AA是QQ的前綴(不一定要是properproper前綴). 比如串 abababab 和 abababababab 都是串a(chǎn)bababaabababa的周期. 串A的最大周期就是它最長的一個(gè)周期或者是一個(gè)空串(當(dāng)A沒有周期的時(shí)候), 比如說,abababababab的最大周期是abababab. 串a(chǎn)bcabc的最大周期是空串. 給出一個(gè)串,求出它所有前綴的最大周期長度之和.

輸入格式

第一行一個(gè)整數(shù)k(1<k<1000000)k(1<k<1000000)表示串的長度. 接下來一行表示給出的串.

輸出格式

輸出一個(gè)整數(shù)表示它所有前綴的最大周期長度之和.

樣例

樣例輸入

Copy

8 babababa

樣例輸出

Copy

24

code

Copy

#include<bits/stdc++.h> using namespace std; const int maxn=1e6+5; int n; long long sum,fail[maxn]; char a[maxn]; int main(){ scanf("%d %s ",&n,a+1); for(int i=2,j=0;i<=n;i++){ while(j&&a[i]!=a[j+1])j=fail[j]; if(a[i]==a[j+1])j++; fail[i]=j; } for(int i=1,j;i<=n;i++){ j=i; while(fail[j])j=fail[j]; // if(fail[i])fail[i]=j; sum+=i-j; } cout<<sum; }