OKR

题目描述

一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串PP是串AA的前缀, 当且仅当存在串BB, 使得A=PBA=PB. 如果 P!=AP!=A 并且PP不是一个空串,那么我们说PP是AA的一个properproper前缀. 定义QQ 是AA的周期, 当且仅当QQ是AA的一个properproper 前缀并且AA是QQ的前缀(不一定要是properproper前缀). 比如串 abababab 和 abababababab 都是串abababaabababa的周期. 串A的最大周期就是它最长的一个周期或者是一个空串(当A没有周期的时候), 比如说,abababababab的最大周期是abababab. 串abcabc的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.

输入格式

第一行一个整数k(1<k<1000000)k(1<k<1000000)表示串的长度. 接下来一行表示给出的串.

输出格式

输出一个整数表示它所有前缀的最大周期长度之和.

样例

样例输入

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; }