自动搬运

查看原文

来自洛谷，原作者为

	皎月半洒花 在那之前，你要多想。

搬运于2025-08-24 22:13:23，当前版本为作者最后更新于2019-12-10 16:37:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

PAM为啥总感觉比SAM友善好多啊

与另一篇题解做法不同，我们可以直接对两个串同时建立$\rm PAM$。考虑$\rm PAM$里面每个节点的意义，节点=回文串，所以考虑我们对两个$\rm PAM$同时开始$\sf dfs$，因为起始状态相同，那么如果遇到相同的转移就说明有相同的状态，把$sz_x\times sz_y$作为贡献加到答案里面即可。

以下是一些闲扯：

• 注意到，对于回文串之间的转移而言，由于从奇数长度只能转移到奇数长度，偶数长度只能转移到偶数长度，所以要把每一组根都$\sf dfs$一遍。

• 紧接着上一条，显然我们要特判掉虚根（即奇根和偶根）。

• 然后这道题的两个 子$\mathsf {idea}$ 分别跟下面两题相似：

  • Link1，Link2

上代码

#define Sigma 30
#define MAXN 500010
#define LL long long

using namespace std ;
int N, M ; LL ans ; char S[MAXN], T[MAXN] ;
struct PAM{
	int rt0, rt1, last, sz, f[MAXN] ;
	int trie[MAXN][Sigma], pre[MAXN], len[MAXN] ;
	void Init(){
		sz = -1, rt0 = ++ sz, rt1 = ++ sz ; 
		pre[rt0] = pre[rt1] = rt1, len[rt0] = 0, len[rt1] = -1, last = rt0 ; 
	} 
	void Insert(int x, int p, char *s){
		int u = last ; 
		while (s[p] != s[p - len[u] - 1]) u = pre[u] ; 
		if (!trie[u][x]){
			int newq = ++ sz, fa = pre[u] ; 
			while (s[p] != s[p - len[fa] - 1]) fa = pre[fa] ;
			pre[newq] = trie[fa][x], trie[u][x] = newq, len[newq] = len[u] + 2 ;
		}
		last = trie[u][x], f[last] ++ ; 
	}
}P, Q ;
void dfs(int x, int y){
	if (x + y > 2) ans += 1ll * P.f[x] * Q.f[y] ; 
	for (int i = 1 ; i <= 26 ; ++ i)
		if (P.trie[x][i] && Q.trie[y][i]) dfs(P.trie[x][i], Q.trie[y][i]) ;
}
int main(){
	P.Init(), Q.Init() ;
	cin >> (S + 1) >> (T + 1) ; 
	N = strlen(S + 1), M = strlen(T + 1) ;
	for (int i = 1 ; i <= N ; ++ i) P.Insert(S[i] - 'A' + 1, i, S) ;
	for (int i = 1 ; i <= M ; ++ i) Q.Insert(T[i] - 'A' + 1, i, T) ;
	for (int i = P.sz ; i ; -- i) P.f[P.pre[i]] += P.f[i] ; 
	for (int i = Q.sz ; i ; -- i) Q.f[Q.pre[i]] += Q.f[i] ; 
	dfs(1, 1) ; dfs(0, 0) ; cout << ans<< endl ; return 0 ;
}