【洛谷P5555】秩序魔咒【回文自动机】

Description

• 传送门
• 给定两个字符串，求同时是这两个字符串的子串的回文子串的最大长度以及是这个长度的本质不同的字符串数量。

Solution

要求是回文子串，考虑对两个字符串分别建出回文自动机，然后同时在起点出发((odd)或(even))，始终按照相同字符的转移走，那么一定走到的是二者都含有的子串，沿途经过的点就是符合条件的回文子串了。于是用(bfs)或(dfs)实现均可，博主使用的是(bfs)方法，就先将(0)和(1)(push)进队列中，然后不断取出队首，更新答案，枚举儿子是否能走即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef pair<int,int> pii;
#define mp make_pair
int n,m;
struct PAM{
	char s[N];
	int fail[N],len[N],ch[N][26];
	int last,tot;
	inline void init(){
		len[0]=0;len[1]=-1;
		fail[0]=fail[1]=1;
		last=0;tot=1;
	}
	inline void newnode(int x,int p,int v){
		ch[p][v]=++tot;len[tot]=len[p]+2;
		if(p==1) fail[tot]=0;
		else{
			p=fail[p];
			while(s[x-len[p]-1]!=s[x]) p=fail[p];
			fail[tot]=ch[p][v];
		}
	}
	inline void insert(int x){
		int p=last,v=s[x]-'a';
		while(s[x-len[p]-1]!=s[x]) p=fail[p];
		if(!ch[p][v]) newnode(x,p,v);
		last=ch[p][v];
	}
}A,B;
int main(){
	scanf("%d%d",&n,&m);
	scanf("%s%s",A.s+1,B.s+1);
	A.init();B.init();
	for(int i=1;i<=n;++i) A.insert(i);
	for(int i=1;i<=m;++i) B.insert(i);
	queue<pii> q;q.push(mp(0,0));q.push(mp(1,1));
	int ans=0,cnt=0;
	while(!q.empty()){
		int p1=q.front().first,p2=q.front().second;q.pop();
		if(A.len[p1]>ans) ans=A.len[p1],cnt=0;
		if(A.len[p1]==ans) cnt++;
		for(int i=0;i<26;++i)
			if(A.ch[p1][i]&&B.ch[p2][i]) q.push(mp(A.ch[p1][i],B.ch[p2][i]));
	}
	printf("%d %d
",ans,cnt);
	return 0;
}