秩序魔咒
题意:
求两个串最长相同的回文子串的长度,并求出这种长度的子串有多少个
思路:
- 既然有回文串,自然会想到回文自动机或 manacher,而用回文自动机会变得非常板子!
- 最长的很容易处理,而要在两个串中都出现,我们可以像后缀自动机那样将两个串连在一起,中间用两个不同且不会出现的字符连接(由于回文自动机内部要调用这个字符串,因此必须真正的将字符串进行连接)。
- 然后对前后的回文串打上不同的标记,最后统计在两个字符串中都出现过的回文子串即可。
题面描述
#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
const int maxn = 6e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;
string s1, s2, s;
int ch[maxn][28], fail[maxn], len[maxn], cnt[maxn][2];
int last, sz, pos, n, m;
void init() {
fail[0]=fail[1]=sz=last=1;
len[1]=pos=-1;
}
void add(int c, int f) {
++pos; int p=last;
while(s[pos-len[p]-1]!=s[pos]) p=fail[p];
if(!ch[p][c]) {
int np=++sz, fp=fail[p];
len[np]=len[p]+2;
while(s[pos-len[fp]-1]!=s[pos]) fp=fail[fp];
fail[np]=ch[fp][c];
ch[p][c]=np;
}
last=ch[p][c];
cnt[last][f]++;
}
int main() {
//ios::sync_with_stdio(false);
n=read(), m=read();
init();
cin>>s1>>s2;
s=s1+"12"+s2;
for(int i=0; i<s.size(); ++i) {
if(s[i]=='1') add(26,0);
else if(s[i]=='2') add(27,1);
else if(i<n) add(s[i]-'a',0);
else add(s[i]-'a',1);
}
int mx=0, ans=0;
for(int i=sz; i>=0; --i) {
if(cnt[i][0]&&cnt[i][1]) {
if(len[i]>mx) mx=len[i], ans=1;
else if(len[i]==mx) ans++;
}
}
printf("%d %d\n", mx, ans);
}