回文子串对(扩展kmp-kmp与回文子串)

Problem 1 回文子串对(manacher.cpp/c/pas)

【题目描述】

给定一长度为n的小写字母串，求有多少对回文子串，它们的交集非空。

一对回文子串的交集非空：[a,b]、[c,d](a≠c或b≠d)为2个回文子串，且[a,b]∩[c,d]≠?。

【输入格式】

第一行一个整数n表示串长。

第二行长度为n的小写字母串。

【输出格式】

输出一个整数表示答案，答案对1000000007取模。

【样例输入】

4

babb

【样例输出】

6

【数据范围】

对于30%的数据，n<=1000

另有10%的数据，串里仅含一种字母。

对于100%的数据，n<=2*10^6

找到最前面的max(r[j]+j),映射过去

设r[i]表示以i点为中心点的最长回文子串

则如图：

#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<iostream>#include<functional>#include<algorithm>using namespace std;#define F (1000000007)#define MAXN (2000000+10)using namespace std;long long r[MAXN],n,L[MAXN][2],R[MAXN][3];char s[MAXN];int main(){freopen("manacher.in","r",stdin);freopen("manacher.out","w",stdout);scanf("%d%s",&n,s+1);memset(r,0,sizeof(r));memset(L,0,sizeof(L));memset(R,0,sizeof(R));int j=0;for (int i=1;i<=n;i++){if (r[j]+j>i) r[i]=min(r[j-(i-j)],j+r[j]-i);while (i-r[i]>1&&i+r[i]<n&&s[i-r[i]-1]==s[i+r[i]+1]) r[i]++;if (r[i]+i>r[j]+j) j=i;L[i-r[i]][0]+=1;L[i+1][0]-=1;R[i][0]++;R[i+r[i]+1][0]--;}//for (int i=1;i<=n;i++) cout<<r[i]<<' ';cout<<endl;j=0;memset(r,0,sizeof(r));for (int i=1;i<n;i++){if (r[j]+j>i) r[i]=min(r[j-(i-j)],j+r[j]-i);while (i-r[i]>0&&i+r[i]<=n&&s[i+1-r[i]-1]==s[i+r[i]+1]) r[i]++;if (r[i]+i>r[j]+j) j=i;L[i+1-r[i]][0]+=1;L[i+1][0]-=1;R[i+1][0]++;R[i+r[i]+1][0]--;}/*for (int i=1;i<=n;i++) cout<<L[i][0]<<' ';cout<<endl;for (int i=1;i<=n;i++) cout<<R[i][0]<<' ';cout<<endl;*/for (int i=1;i<=n;i++) L[i][1]=L[i][0]+L[i-1][1];for (int j=1;j<=2;j++)for (int i=1;i<=n;i++)R[i][j]=R[i-1][j]+R[i][j-1];long long ans=0;for (int i=1;i<=n;i++)ans=(ans+L[i][1]*R[i-1][2])%F;long long tot=0;if (R[n][2]%2) tot=(((R[n][2]-1)/2)%F)*((R[n][2])%F)%F;else tot=(((R[n][2])/2)%F)*((R[n][2]-1)%F)%F;//cout<<tot<<' '<<ans<<endl;cout<<((tot-ans+F)%F)<<endl;return 0;}