回文子串对(扩展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点为中心点的最长回文子串
则如图：
 
 
[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.zzzyk.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;  
}

补充：软件开发 , C++ ,