洛谷P5555 秩序魔咒题解

题意：

现代魔法师小L和小K正在研究魔咒。

“你知道如何使用魔咒吗？”

“当然知道，这是一个现代魔法师最基本的修养。”

“那你对魔咒的发展史了解多少？”

“课上讲的我还记得一点。那是在很久很久之前了。当时，世界上还没有人会使用魔咒，而混沌魔法成为了魔法界当时的主流魔法。这是一种邪恶的法术，不需要技巧，不需要规则，内心越黑暗，力量越强。于是，邪恶的魔法师们自相残杀，弄得天昏地暗，血流成河。其中，以自称‘混沌恶魔’的魔法师为首的魔法师集团通过极其肮脏的手段控制了几乎整个魔法界，让那些向往秩序与和平的魔法师难以生存。就在这个时候，世界救星的救星出现了。名为莱赫穆拉和肯埋多卡的两名魔法师勇敢地站了出来，仅凭两个人的力量就与混沌恶魔集团展开了决战，可终究寡不敌众，被逼到了绝境。就在混沌恶魔的最后一击打中他们的身体时，莱赫穆拉和肯埋多卡利用这一击的巨大魔力，将两人余下的全部魔法与意志升格成了概念，创造了秩序魔咒体系，扭转了世界理论，使得混沌魔法被永远封印。而混沌恶魔也在这强烈的扭曲中灰飞烟灭。从此，魔法界由混沌纪元进入了秩序纪元，人们遵循莱赫穆拉和肯埋多卡这两位圣人的遗志，在秩序魔咒体系下使用魔咒，直到现在。”

“原来是这样。我们如今需要遵循一系列原则来使用魔咒，是这个原因啊。”

“是啊，这正是两位圣人为维持现在这个世界不退回混沌纪元而做的努力。话说，你是上个星期才刚刚上了第一堂魔法课，你还记得使用魔咒的几个原则吗？”

“我想想。第一，必须出现在秩序序列中。当时二位圣人留下来的体系，经过后代魔法师不懈的努力，被翻译成了名为秩序序列的存在。为了方便现代魔法师使用，秩序序列只由英文小写字母组成。由于体系的力量过于强大而不能仅仅限制在一个序列中，魔法师们分别将两位圣人的遗志转移到了两个秩序序列里。魔咒必须受到秩序序列的限制。具体来说，是必须出现在秩序序列里（是秩序序列的子串）。由于二位圣人的遗志不可分割，魔咒必须同时出现在两个秩序序列里。第二，为了让魔咒稳定而精确，秩序体系规定了魔咒的形态。具体来说，魔咒的第一个字符需要与魔咒的倒数第一个字符相同，魔咒的第二个字符需要与魔咒的倒数第二个字符相同，以此类推。这样就可以使魔咒对称而有秩序了。还有的话，让我看看……”

“别看了别看了，最重要的就是这些了。还有，你说不定还不知道，魔咒越长，力量越强大。”

“是这样的吗？难怪那天老师演示的魔咒魔力比我的大那么多。”

“是的是的。你是不是已经发现了，魔咒的力量是有最高限制的？”

“啊，好像没错。但老师那天说，最强魔咒的使用者还没出现？”

“对。使用者自身必须要有与魔咒同样程度的能力，才可能顺利地使用这个魔咒。我们这些初学者，不知道何年何月才能达到这个程度呢……”

“唉……不如，我们来数一数力量最强的魔咒的长度，和它们有多少个吧。”

“嗯，反正没事可做，我们就来干一干这种力所能及的事吧。”

于是，小L和小K就开始数最强魔咒的长度和个数。可过了不一会儿，它们就坚持不住了，因为秩序序列实在太长太长了。

现在，你作为一个资深魔法师，有必要告诉他们这种基本的常识。你当然已经知道两个秩序序列的形态，请你帮小L和小K算出最强魔咒的长度和个数。

输入格式：

第一行，两个整数\(n,m\)，分别表示两个秩序序列的长度。

接着第二行与第三行，两个字符串，表示两个秩序序列，长度分别为\(n,m\)。

输出格式：

一行两个整数，用单个空格隔开，分别表示最强魔咒的长度与个数。

数据范围：

\(1 \le n,m \le 260817\) 。

显然，相同的魔咒数量只计一次。

保证至少存在一个长度不小于\(1\)的符合规定的魔咒。时限为 3s。

这道题用 PAM （回文自动机）做会非常简单。

众所周知，回文自动机的每个节点都是一个回文串。

那么我们先对第一个串建回文自动机，并标记每个节点

然后把这个回文自动机看作空的，再对第二个建回文自动机。

这样，两轮都会被经过的节点，就是满足条件的节点。

时间复杂度 \(\mathcal{O}(n)\) ，以及实际空间复杂度 \(\mathcal{O}(2n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(6e5 + 15))

char s[N], ok[2][N];
int tot, mx, cnt, fail[N], len[N], ch[N][26];
int getfail(int p, int i)
{
    while(s[i - len[p] - 1] != s[i]) p = fail[p];
    return p;
}
void solve(int type)
{
    for(int i = 1, p, c; s[i]; i++)
    {
        c = s[i] - 'a'; p = i > 1 ? getfail(p, i) : 0;
        if(!ch[p][c])
        {
            ch[p][c] = ++tot; len[tot] = len[p] + 2; 
            fail[tot] = p > 0 ? ch[getfail(fail[p], i)][c] : 1;
        }
        p = ch[p][c]; ok[type][p] = true;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m; 
    fail[tot = 1] = 0; len[0] = -1;
    cin >> (s + 1); solve(0);
    cin >> (s + 1); solve(1);
    for(int i = 2; i <= tot; i++)
        if(ok[0][i] && ok[1][i]) {
            if(len[i] > mx) { mx = len[i]; cnt = 1; }
            else if(len[i] == mx) ++cnt;
        }
    cout << mx << ' ' << cnt << '\n';
    return 0;
}