Codeforces 17E Palisection 【Manacher】
8611 ワード
Codeforces 17E Palisection
E. Palisection
In an English class Nick had nothing to do at all, and remembered about wonderful strings called palindromes. We should remind you that a string is called a palindrome if it can be read the same way both from left to right and from right to left. Here are examples of such strings: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».
Nick started to look carefully for all palindromes in the text that they were reading in the class. For each occurrence of each palindrome in the text he wrote a pair — the position of the beginning and the position of the ending of this occurrence in the text. Nick called each occurrence of each palindrome he found in the text subpalindrome. When he found all the subpalindromes, he decided to find out how many different pairs among these subpalindromes cross. Two subpalindromes cross if they cover common positions in the text. No palindrome can cross itself.
Let’s look at the actions, performed by Nick, by the example of text «babb». At first he wrote out all subpalindromes:
• «b» — 1..1 • «bab» — 1..3 • «a» — 2..2 • «b» — 3..3 • «bb» — 3..4 • «b» — 4..4 Then Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six: 1..1 cross with 1..3 1..3 cross with 2..2 1..3 cross with 3..3 1..3 cross with 3..4 3..3 cross with 3..4 3..4 cross with 4..4 Since it’s very exhausting to perform all the described actions manually, Nick asked you to help him and write a program that can find out the amount of different subpalindrome pairs that cross. Two subpalindrome pairs are regarded as different if one of the pairs contains a subpalindrome that the other does not.
Input
The first input line contains integer n (1 ≤ n ≤ 2·106) — length of the text. The following line contains n lower-case Latin letters (from a to z).
Output
In the only line output the amount of different pairs of two subpalindromes that cross each other. Output the answer modulo 51123987.
Examples
input
4 babb
output
6
input
2 aa
output
2
気持ち悪くてたまらない
2つの文字列の位置関係では、文字列の右端点が他の文字列の左端点よりも厳密に小さい場合のみ減少します.したがって、2つの列の関係は最大1回しか減少しません.
意味のない状況を排除する必要があります差分計算貢献も必要で、逆さまに走ることに注意します
また、文字列と文字の交差を単独で考慮する必要があります.法則を探して接頭辞と和を求めればいいです.
接頭辞和:私たちは1つの点に対して、最長の回文列しか求めていないため、またこの回文列に含まれる小さな回文列(同一中心)の左右のノードの変化は毎回アルカリ2を加えるかアルカリ2を加えるので、接頭辞と求めることができる
E. Palisection
In an English class Nick had nothing to do at all, and remembered about wonderful strings called palindromes. We should remind you that a string is called a palindrome if it can be read the same way both from left to right and from right to left. Here are examples of such strings: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».
Nick started to look carefully for all palindromes in the text that they were reading in the class. For each occurrence of each palindrome in the text he wrote a pair — the position of the beginning and the position of the ending of this occurrence in the text. Nick called each occurrence of each palindrome he found in the text subpalindrome. When he found all the subpalindromes, he decided to find out how many different pairs among these subpalindromes cross. Two subpalindromes cross if they cover common positions in the text. No palindrome can cross itself.
Let’s look at the actions, performed by Nick, by the example of text «babb». At first he wrote out all subpalindromes:
• «b» — 1..1 • «bab» — 1..3 • «a» — 2..2 • «b» — 3..3 • «bb» — 3..4 • «b» — 4..4 Then Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six:
Input
The first input line contains integer n (1 ≤ n ≤ 2·106) — length of the text. The following line contains n lower-case Latin letters (from a to z).
Output
In the only line output the amount of different pairs of two subpalindromes that cross each other. Output the answer modulo 51123987.
Examples
input
4 babb
output
6
input
2 aa
output
2
気持ち悪くてたまらない
2つの文字列の位置関係では、文字列の右端点が他の文字列の左端点よりも厳密に小さい場合のみ減少します.したがって、2つの列の関係は最大1回しか減少しません.
意味のない状況を排除する必要があります差分計算貢献も必要で、逆さまに走ることに注意します
また、文字列と文字の交差を単独で考慮する必要があります.法則を探して接頭辞と和を求めればいいです.
接頭辞和:私たちは1つの点に対して、最長の回文列しか求めていないため、またこの回文列に含まれる小さな回文列(同一中心)の左右のノードの変化は毎回アルカリ2を加えるかアルカリ2を加えるので、接頭辞と求めることができる
#includeif(pos>i)x=min(p[id*2-i],pos-i+1);
else x=1;
while(s[i-x]==s[i+x])x++;
x--;
if(x+i>pos)pos=x+i,id=i;
p[i]=x;
}
}
int main(){
scanf("%d%s",&len,t);
s[n=0]='!';
for(int i=0;is[++n]='#',s[++n]=t[i];
s[++n]='#';s[++n]='?';
Manacher();
int ans=0,tmp=0;
for(int i=1;iif(p[i]==0&&s[i]=='#')continue;
if(p[i]==1&&s[i]!='#')continue;
// ，
r[i-p[i]-1]--;r[i-1]++;//
tmp=(tmp+p[i]/2)%Mod;
}
//r
//r
//r
for(int i=n-1;i>0;i--)r[i]+=r[i+1];
for(int i=n-1;i>=1;i--){
if(i&1)r[i]=r[i+1];
else r[i]=(r[i]+r[i+1])%Mod;
}
for(int i=n-3;i>0;i--)r[i]=(r[i]+r[i+2])%Mod;
ans=1ll*tmp*(tmp-1)/2%Mod;
for(int i=1;iif(p[i]==0&&s[i]=='#')continue;
if(p[i]==1&&s[i]!='#')continue;
ans-=r[i+3]-r[i+p[i]+3];
ans=(ans%Mod+Mod)%Mod;
}
//
for(int i=2;i2])%Mod;
for(int i=1;i%Mod;
printf("%d",ans);
return 0;
}