秩序魔咒（回文自动机+最长公共回文子串）

秩序魔咒

题意：
求两个串最长相同的回文子串的长度，并求出这种长度的子串有多少个

思路：

1. 既然有回文串，自然会想到回文自动机或 $manacher$manacher，而用回文自动机会变得非常板子！
2. 最长的很容易处理，而要在两个串中都出现，我们可以像后缀自动机那样将两个串连在一起，中间用两个不同且不会出现的字符连接（由于回文自动机内部要调用这个字符串，因此必须真正的将字符串进行连接）。
3. 然后对前后的回文串打上不同的标记，最后统计在两个字符串中都出现过的回文子串即可。

题面描述

#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);
}