題目描述

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

輸入格式

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

輸出格式

輸出一個整數(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; }