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

题意

我们说串$a$和串$b$不等价是说$a!=b$且$a!=rev(b)$

其中$rev(b)$是$b$的反转串

从$s$串中选出最多的子串,使得任意两个子串都不等价。

原问题相当于,某个子串和它的反串只能计算一次贡献

考虑把原串和反串拼起来变成$s\#rev(s)$

其中$s$是原串,$rev(s)$是反串

$s$的所有本质不同子串在$s$中计算过了一遍

若某个子串的反串没在$s$中出现过,会在$rev(s)$中再次计算贡献

等价于,这个子串和反串分别在$s$和$rev(s)$分别计算了一遍

若某个子串的反串在$s$中出现过,那么$rev(s)$中不再会计算贡献

等价于,这个子串和反串在$s$中分别计算了一次

对$s\#rev(s)$求出来的本质不同子串,就是答案的两倍。

等等…不对劲,如果子串$a$是一个回文串

那么这个回文串无论如何只会被计算到一次,没有计算两次…

那么用$PAM$求出原串有多少回文串即可

#include 
   
    using namespace std;typedef long long ll;const int maxn = 8e6+10;int n,m;struct SAM{
   	int zi[maxn][30],fa[maxn],len[maxn],ed=1,id=1;	void insert(int c)	{
   		int p = ed, np = ++id; ed = np;		len[np] = len[p]+1;		for( ; p&&!zi[p][c];p=fa[p] )	zi[p][c] = np;		if( p==0 )	fa[np] = 1;		else		{
   			int q = zi[p][c];			if( len[q]==len[p]+1 )	fa[np] = q;			else			{
   				int nq = ++id;				memcpy( zi[nq],zi[q],sizeof zi[nq] );				len[nq] = len[p]+1, fa[nq] = fa[q];				fa[q] = fa[np] = nq;				for( ; p&&zi[p][c]==q;p=fa[p] )	zi[p][c] = nq; 			}		}	}	ll get(char a[])//得到a所有本质不同的子串个数 	{
   		int l = strlen( a+1 );		ll ans = -(1ll*l/2+1)*(l/2+1);		for(int i=1;i<=l;i++)	insert( a[i]-'a' );		for(int i=1;i<=id;i++)	ans += len[i]-len[fa[i]];	//	cout << "SAM:" << ans << endl;		return ans;	} }sam;struct PAM{
   	int zi[maxn][30],fail[maxn],id,las,len[maxn];	PAM()	{
   		las = id = 1; fail[0] = 1, fail[1] = 1;		len[0] = 0, len[1] = -1;		}	int get_fail(int u,int index,char a[])	{
   		while( a[index]!=a[index-len[u]-1] )	u = fail[u];		return u;	}	void insert(int c,int index,char a[])	{
   		int u = get_fail(las,index,a);		if( !zi[u][c] )		{
   			int now = ++id, v = get_fail(fail[u],index,a);			len[now] = len[u]+2;			fail[now] = zi[v][c], zi[u][c] = now;		}		las = zi[u][c];	}	ll get(char a[] )	{
   		int l = strlen( a+1 );		for(int i=1;i<=l;i++)	insert( a[i]-'a',i,a );	//	cout << "PAM:" << id-1 << endl;		return id-1;	}}pam;char a[maxn],b[maxn];int main(){
   	cin >> ( a+1 );	int len = strlen( a+1 );	b[1+len] = '#';	for(int i=1;i<=len;i++)	b[i] = a[i], b[i+len+1] = a[len-i+1];	cout << ( sam.get(b)+pam.get(a) )/2;}
   

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