本文共 3381 字，大约阅读时间需要 11 分钟。

题意

给定串$s$和串$t$

要求在$s$中找一个子串$s^{\prime }$(不需要本质不同),$t$中找一个前缀$t^{\prime }$

满足$s^{\prime }$长度大于$t^{\prime }$,使得$s^{\prime }+t^{\prime }$是一个回文串,求方案数

好像这题用$exkmp+mancher$就是裸题??

update:我是个憨批,用后缀数组的话更是裸题

因为我们实际上只需要知道$s$的每个前缀的反串和$t$的$lcp$长度

于是可以对$s$的反串和$t$连在一起跑后缀数组,套个$RMQ$就能求$lcp$了

因为$s^{\prime }$长度大于等于$t^{\prime }$

所以$s^{\prime }$可以分为两部分,即$s^{\prime }=s_1^{\prime }+s_2^{\prime }$

其中$s_1^{\prime }$是$t^{\prime }$的反串,$s_2^{\prime }$是一个回文串

那么我们可以枚举串$s$的位置$i$,让$i$变成$s_1^{\prime }$的结束位置即可

于是问题转化为求出

①.$i+1$开头的回文串个数

②.以$i$结尾并等于$t$串某个前缀的子串个数

首先①很好求,对反串建回文树即可

②的话,考虑对$s$建立回文自动机

存下$s$每个前缀$s[1...i]$的节点记作$ID[i]$

然后把反串$t$放在$SAM$上跑,最后我们会得到一个节点$p$和匹配长度$L$

于是$s[1...L]$在节点$p$中出现过一次

我们还想知道$s[1...L-1]$在哪些节点中出现过

因为刚才我们是插入的反串,所以现在相当于删除匹配的第一个字母

$SAM$是支持删除的,直接让$L--$,然后跳后缀链接即可

最后因为一个串在父亲节点出现也会在儿子节点出现,所以还需要来一遍dfs/拓扑

#include 
   
    using namespace std;const int maxn = 3e6+10;int l[maxn],fa[maxn],zi[maxn][30],id=1,las=1,ID[maxn];char s[maxn],t[maxn];void insert(int c){
   	int p = las,np = ++id; las = id;	l[np] = l[p]+1; ID[l[np]] = np;	for( ; p&&zi[p][c]==0 ;p=fa[p] )	zi[p][c] = np;	if( !p )	fa[np] = 1;	else	{
   		int q = zi[p][c];		if( l[q]==l[p]+1 )	fa[np] = q;		else		{
   			int nq = ++id; fa[nq] = fa[q],l[nq] = l[p]+1;			memcpy( zi[nq],zi[q],sizeof zi[nq] );			fa[np] = fa[q] = nq;			for( ; p&&zi[p][c]==q ;p=fa[p] )	zi[p][c] = nq;			}	}}int rk[maxn],c[maxn],f[maxn],h[maxn];vector
    
     vec[maxn];void dfs(int u){
   	for(auto v:vec[u] )			f[v] += f[u], dfs(v);}void chiken_sort(){
   	for(int i=2;i<=id;i++)	vec[fa[i]].push_back( i );	dfs(1);}struct PAM{
   	int zi[maxn][30],fail[maxn],l[maxn],id,las,cnt[maxn];	PAM()	{
   		fail[0] = 1, fail[1] = 1, l[0] = 0, l[1] = -1;		las = id = 1;	}	int get_fail(int u,int index)	{
   		while( s[index]!=s[index-l[u]-1] )	u = fail[u];		return u;	}	void insert(int c,int index)	{
   		int u = get_fail(las,index);		if( zi[u][c]==0 )		{
   			int now = ++id, v = get_fail(fail[u],index);			l[now] = l[u]+2; 			fail[now] = zi[v][c]; zi[u][c] = now;			cnt[now] = cnt[fail[now]]+1;		}		las = zi[u][c];	}}pam;int main(){
   	scanf("%s%s",s+1,t+1);	int n = strlen( s+1 ),m = strlen( t+1 );	for(int i=1;i<=n;i++)	insert( s[i]-'a' );		int p = 1, L = 0;	for(int i=m;i>=1;i--)	{
   		int c = t[i]-'a';		if( zi[p][c] )	p = zi[p][c],L++;		else		{
   			while( p && !zi[p][c] )	p = fa[p];			if( !p )	p = 1, L = 0;			else	L = l[p]+1, p = zi[p][c];			}	}	while( L )	{
   		f[p]++; L--;		if( L==l[fa[p]] )	p = fa[p];	}	chiken_sort();		reverse(s+1,s+1+n);	for(int i=1;i<=n;i++)	{
   		pam.insert( s[i]-'a',i );		h[n-i+1] = pam.cnt[pam.las];	}	long long ans = 0;	for(int i=1;i<=n;i++)		ans += 1ll*f[ID[i]]*h[i+1]; 	cout << ans;}
    
   

也可以换一种$SAM$写法

直接拿反串$t$在$s$的自动机上跑到$p$节点,匹配长度$L$

考虑对长度为$1,2...L$的前缀$t$串都算一次贡献,这些串我们只需要跳后缀链接就可以得到

比如在当前在节点$p$,那么我们需要对长度为$l[f{a}_p]+1...l[p]$的这些$t$前缀都算一次贡献

贡献就是这些串后的回文个数和

我们在创建$SAM$的时候给新建节点$np$一个权值

因为$np$节点代表的是$s[1...i]$,所以它的权值赋为$i+1$开头的回文串个数

这样我们最后对$SAM$做一遍dfs/拓扑就可以得到节点内每个串在原串$s$中作为不同的$endpos$时的$i+1$开头的回文串个数和

这样就可以统计啦!!

感觉比我上面的做法要难理解

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116713405 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！