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點為中心點的最長回文子串
則如圖：
[cpp]
#include
#include
#include
#include
#include
#include
#include
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]
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<
j=0;memset(r,0,sizeof(r));
for (int i=1;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<
for (int i=1;i<=n;i++) cout<
*/
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; www.2cto.com
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<
cout<<((tot-ans+F)%F)<
return 0;
}
