题意:给你2个串(长度1e6),在第一个串里找“s1s2s3”,第二个串里找“s4”,拼接后,是一个回文串,求方案数
题解:知道s1和s4回文,s2和s3回文,所以我们枚举s1的右端点,s1的长度乘以s2起始点为左边界的回文串的数量,累加就是答案。
所以先求s1,再求以每个点为左边界的回文串的数量
就是求每个后缀匹配第二个串的LCP(扩展kmp,或者hash+二分)二的话,后面部分用(Manacher+前缀和)就可以解决
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+;
char str[maxn*],t[maxn*],s[maxn*];
int dp[maxn*],dpnext[maxn*],dpret[maxn*],suffix[maxn*],last[maxn];
void manacher(char tmp[],int length,int rad[])
{
for(int i=,j=,k;i<length;i+=k)
{
while(tmp[i-j-]==tmp[i+j+]) j++;
rad[i]=j;
for(k=;k<=rad[i]&&rad[i-k]!=rad[i]-k;++k)
{
rad[i+k]=min(rad[i-k],rad[i]-k);
}
j=max(j-k,);
}
}
void ExtendedKMP(char *a,char *b,int M,int N,int *Next,int *ret)
{
int i,j,k;
for(j=;+j<M&&a[j]==a[+j];j++);
Next[]=j;
k=;
for(i=;i<M;i++)
{
int Len=k+Next[k],L=Next[i-k];
if(L<Len-i)
{
Next[i]=L;
}
else
{
for(j=max(,Len-i);i+j<M&&a[j]==a[i+j];j++);
Next[i]=j;
k=i;
}
}
for(j=;j<N&&j<M&&a[j]==b[j];j++);
ret[]=j;
k=;
for(i=;i<N;i++)
{
int Len=k+ret[k],L=Next[i-k];
if(L<Len-i)
{
ret[i]=L;
}
else
{
for(j=max(,Len-i);j<M&&i+j<N&&a[j]==b[i+j];j++);
ret[i]=j;
k=i;
}
}
}
int main()
{
int i,j,k,n,m,lens,lent;
scanf(" %s",str);
scanf(" %s",t);
lens=strlen(str);
lent=strlen(t);
reverse(str,str+lens);
s[]='(';s[]='#';
for(i=,j=;i<lens;i++,j+=)
{
s[j]=str[i];
s[j+]='#';
}
n=lens;
lens=lens*+;
s[lens-]=')';
manacher(s,lens,dp);
ExtendedKMP(t,str,lent,n,dpnext,dpret);
suffix[lens]=;
memset(last,,sizeof(last));
for(i=;i<lens-;i++)
{
long long maxdis;
if(i%==)
{
maxdis=i/+dp[i]/-;
last[maxdis]++;
last[i/-]--;
}
else
{
maxdis=i/+dp[i]/-;
if(dp[i]/>)
{
last[maxdis]++;
last[i/-]-- ;
}
}
}
suffix[n]=;
for(i=n-;i>=;i--)
suffix[i]=suffix[i+]+last[i];
long long ans=;
for(i=;i<n;i++)
{
long long len=dpret[i];
ans=ans+len*(suffix[i-]);
}
printf("%lld\n",ans);
}