P6216 回文匹配

KMP+manacher：https://www.luogu.com.cn/problem/P6216

对于一对字符串 \((s_1,s_2)\)，若 \(s_1\) 的长度为奇数的子串 \((l,r)\) 满足 \((l,r)\) 是回文的，那么 \(s_1\) 的“分数”会增加 \(s_2\) 在 \((l,r)\) 中出现的次数。
现在给出一对 \((s_1,s_2),n=|s1|,m=|s2|\)，请计算出 \(s_1\) 的“分数”。
答案对 \(2 ^ {32}\) 取模。

首先因为要求 \((l,r)\) 回文，所以可以用 manacher 求出每一个字符的回文半径，然后根据半径确定以它为对称轴的最长回文串 \((l,r)\)
然后答案要加上 \((l,r),(l+1,r-1),(l+2,r-2),\cdots\) 中 \(s2\) 出现次数和
对于字串 \((l,r)\)，就看区间 \([l,r-m+1]\) 中，有几个字符可以作为 \(s2\) 的开头并与之完全匹配
这一点可以用 kmp 求出，以 \(a_i\) 表示 \(s1_i\) 能否作为 \(s2\) 的开头并和它完全匹配
这里用前缀和，则求每个区间的复杂度是 \(O(1)\)，但区间个数 \(O(n)\)，还要继续优化
表达成式子，方便表示，设 \(L=l,R=r-m+1,maxk=\lfloor\frac{R-L}{2}\rfloor\)：

发现这里的前缀和，也就是 \(sum\) 还是一个区间求和的形式，所以可以求一个二次前缀和（前缀和的前缀和），记之为 \(summ\)
所以原来的式子就是：

所以总复杂度就是 \(O(n)\) 了

题目里说 \((l,r)\) 长度仅限奇数，所以 manacher 时不用像模板一样在字符间隙填充无意义字符
但一开始没看到这点，等注意到时代码都写的差不多了，懒得改了

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<‘0‘||c>‘9‘){if(c==‘-‘) y=0;c=std::getchar();}
	while(c>=‘0‘&&c<=‘9‘){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
#define mod 4294967296ll
int fail[3000005];
char s1[3000005],s2[3000005];
int len1,len2;
int summ[3000005];
char s[6000005];
int n;
int len[6000005];
inline void KMP(){
	fail[1]=0;
	for(reg int j,i=2;i<=len2;i++){
		j=fail[i-1];
		while(j&&s2[j+1]!=s2[i]) j=fail[j];
		if(j) fail[i]=j+1;
		else fail[i]=(s2[1]==s2[i]);
	}
	for(reg int j=0,i=1;i<=len1;i++){
		while(s1[i]!=s2[j+1]&&j) j=fail[j];
		if(s1[i]==s2[j+1]) j++;
		if(j==len2){
			j=fail[j];
			summ[i-len2+1]=1;
		}
	}
}
inline LL manacher(){
	LL ans=0;
	s[0]=1;s[1]=2;n=1;
	for(reg int i=1;i<=len1;i++) s[++n]=s1[i],s[++n]=2;
	s[n+1]=3;
	reg int pos=0,max=0;
	for(reg int L,R,i=1;i<=n;i++){
		if(pos+max-1<i) len[i]=1;
		else len[i]=std::min(len[pos+pos-i],pos+max-i);
		while(s[i+len[i]]==s[i-len[i]]) len[i]++;
		if(i+len[i]-1>=pos+max-1) pos=i,max=len[i];
		L=(i-len[i]+2)>>1;R=((i+len[i]-2)>>1)-len2+1;
//			printf("i : %d, id : %d, len[i] : %d, L : %d, R : %d\n",i,i>>1,len[i],L,R);
		if(s[i]!=2&&R>=L) ans+=summ[R]-summ[R-((R-L)>>1)-1]-summ[L+((R-L)>>1)-1]+summ[std::max(L-2,0)],ans%=mod;
		//长度为奇数 
//			printf("ans : %d\n",ans); 
	}
	return ans%mod;
}
int main(){
	len1=read();len2=read();
	scanf("%s",s1+1);scanf("%s",s2+1);
	if(len1<len2) return puts("0"),0;
	KMP();
	for(reg int i=1;i<=len1;i++) summ[i]+=summ[i-1];
	for(reg int i=1;i<=len1;i++) summ[i]+=summ[i-1];
	printf("%lld",manacher());
	return 0;
}

P6216 回文匹配

原文：https://www.cnblogs.com/suxxsfe/p/13324750.html