manacher

\(\mathrm{manacher}\) 算法可以在线性时间内求出一个串中的最长回文子串。

为了解决偶回文串的中心点非整数，在每个字符之间添加一个字符 #。

为防止越界问题再在串的前后加上奇怪的符号。

记 \(mx\) 为当前最长回文串的右端，\(id\) 为串中心的位置，\(len_{id}\) 为以 \(id\) 为中心最多能向右扩展的长度。

此处 \(mx,my\) 与 \(i,j\) 关于 \(id\) 对称。

• \(i\ge mx\)，令 \(len_i=1\)。

• \(i<mx\)

  • \(len_j\le mx-i\)

    如上图，此时 \(i\) 的最右端还在 \(mx\) 内，令 \(len_i=len_j\) 即可。

  • \(len_j>mx-i\)

    

​ 此时 \(i\) 超过 \(mx\)，对 \(mx\) 进行更新，将中间点 \(id\) 换为 \(i\)，更新回文串长度。

P3805 【模板】manacher

板子如下。

int n;char t[N],s[N<<1];
int len[N<<1];
void getstr(){
	int m=0;s[m++]='@';
	for(int i=1;i<=n;i++)
		s[m++]='#',s[m++]=t[i];
	s[m++]='#',s[n=m]=0;
}
int manacher(){
	int mx=0,id,mxlen=0;
	for(int i=1;i<n;i++){
		if(mx>i)len[i]=min(mx-i,len[2*id-i]);
		else len[i]=1;
		while(s[i+len[i]]==s[i-len[i]])len[i]++;
		if(len[i]+i>mx){
			mx=len[i]+i,id=i;
			mxlen=max(mxlen,len[i]);
		}
	}
	return mxlen-1;
}
int main(){
	scanf("%s",t+1),n=strlen(t+1);
	getstr();
	printf("%d\n",manacher());
	
	return 0;
}

P6216 回文匹配

给出长为 \(n\) 的串 \(s\) 和长为 \(m\) 的串 \(t\)，问有多少四元组 \((l,r,i,j)\) 满足：

• \(1\le l\le i\le j\le r\le n\)。

• \(s[l:r]\) 是奇回文串。

• \(s[i:j]=t\)。

答案对 \(2^{32}\) 取模。

用 \(\mathrm{kmp}\) 跑出每对 \((i,j)\)，\(\mathrm{manacher}\) 跑出所有中心的最长回文串（不需要在中间加特殊字符，因为只要求奇回文串）。

对于 \(t\) 在 \(s\) 中的每个出现，将其下标的值设为 \(1\) 并作前缀和。查询 \(t\) 在 \([l,r]\) 中的出现次数即 \(sum_{r-m+1}-sum_{l-1}\)。

每个回文串都是区间查，所以作二阶前缀和即可。

record