关于一般的回文自动机

回文自动机，由于其指针组成一颗失配树，又名回文树。关于这个算法是谁发现的，并不确切，我最早能追溯到是codeforces上一篇文章。不过至少在七年前，回文自动机应该不流行。例如像hdu3948，统计一个字符串中本质不同的回文串个数，这种模板题，相当部分人的题解是后缀数组，或者Manacher加上哈希。后来这种题目在17年某个网络赛上刻意卡掉了哈希算法，基本就只有自动机的做法了。现在而言，回文自动机已经算是OIer/ICPCer们的基本功了。

普通自动机，实现的细节不再叙述，网上资料也满天飞。这里给出一个模板：

#include <cstdio>
#include <cstring>

using namespace std;

namespace PAM {
    const int N = 500005, M = 26;
    int T[N][M], fail[N], len[N], sz, last, cnt[N];
    char s[N];

    void init() {
        len[0] = 0, len[1] = -1;
        sz = 1, last = 0;
        fail[0] = 1;
        memset(T[0], 0, sizeof(T[0]));
        memset(T[1], 0, sizeof(T[1]));
    }

    int get(int x, int pos) {
        while (pos == len[x] || s[pos - len[x] - 1] != s[pos])
            x = fail[x];
        return x;
    }

     void add(int c, int pos) {
        int t = get(last, pos);
        if (!T[t][c]) {
            len[++sz] = len[t] + 2;
            fail[sz] = T[get(fail[t], pos)][c];
            T[t][c] = sz;
            memset(T[sz], 0, sizeof(T[sz]));
        }
        last = T[t][c];
        cnt[last]++;
    }
}

//for (int i = PAM::sz; i >= 2; i--)
//        PAM::cnt[PAM::fail[i]] += PAM::cnt[i];
using namespace PAM;

其中每个节点都代表一个独一无二的回文子串。指向了该串最大回文后缀的标号。则指向了该串向两边扩展同一个字母得到的新串，则代表了这个回文串的长度，则代表了本回文串出现的次数，一般的题目都会用到。

注意，每一次从左到右字符时，都会从上一个字符所在的回文后缀开始，查看是否可以走匹配，如果不行，则需要不断跳，一直到空或者找到匹配，匹配的话，我们看此时当前这个节点是否存在，不存在就新建。总效率是的，原因在于观察字符串的对称轴的移动，是不会往左的。向右边走的次数当然不超过，而每一次停止，都意味着左右两个字符相匹配。因为我们只添加个字符，所以停止次数也不会超过。

当然这是均摊意义上的。其中少量的时间可能比较大，因为走可能会产生一条链，例如，扩展时便会如此。

Border理论

一些定理

部分参考自：https://zhuanlan.zhihu.com/p/93152631

定义：

1. 是的border，定义为既是的前驱串，又是的后缀串。

2. 是的周期，定义为可以看做个连接再截取前缀的结果（）。

定理1：是的border，当且仅当去掉后面一个得到的字符串，是的周期。

证明简单，可画图，从略。

定理2：是回文串的后缀，是的border当且仅当是回文串。

证明简单，可画图，从略。

定理3：是字符串的border（），是回文串当且仅当是回文串。

证明：是回文，当然是。是回文时，有，因此也是回文的。

证毕

定理4： 是字符串的 border，则去掉后面一个得到的字符串，是的周期，而如果是最小周期，当且仅当是的最长回文真后缀。

这是定理1衍生的，显然。

定理5：是一个回文串，是的最长回文真后缀，是的最长回文真后缀。令分别为满足的字符串，则有下面三条性质：

1. 
2. 如果，那么
3. 如果，那么

这个定理是最重要的一条。会在回文自动机中得到很好应用。

证明摘自：https://xlor.cn/2019/11/mpf/

图片.png

由引理 4的推论， 是 的最小周期， 是的最小周期。考虑反证法，假设 ，因为 是 的后缀，所以 既是 的周期，也是 的周期，而 是 的最小周期，矛盾。所以 。

因为 是 的 border，所以是 的前缀，设字符串，满足 （如下图所示），其中 是 的 border。考虑反证法，假设，那么，所以由引理 3 ， 是回文串，由引理 1 ， 是 的 border，又因为 ，所以，矛盾。所以。

都是 x 的前缀，，所以 。

推论：

的所有回文后缀按照长度排序后，可以划分成段等差数列。

定理6：非空回文字符串如果存在一个回文后缀，那么的形式必然可以表示为的形式。这里为回文串，可以为空串。并且。

证明：

其实由定理4，这个定理的结论基本上接近显然了。这里给出不基于定理4的另一个证明，从另一个角度加以理解。

1. 倘若，，那么令，有，我们如下图构造出了回文字符串和，使得是回文串的回文后缀。如果我们找到了字符串的形式，那么将的右侧的个字符对称过来再拼接到左侧，就可以找到的形式。可以递归下去。

图片.png

2. 倘若，，那么这个情况就很简单，是的形式，符合引理2所言，特殊地，当，也就是时，可表示为两个回文串拼接而成。
   
   图片.png

我们注意到每一次递归，，因此，每次递归回溯，向左侧填充的字符串是完全一样的，都是的形式，于是综上所述。注意，一个回文串重复多次，只是一种特例的情况。

证毕

Border理论的应用

HDU6599 I Love Palindrome String

统计这样的回文串个数：满足自身回文同时满足前个字符组成的也是回文串。

有很多做法：马拉车配合哈希，回文自动机的树上跑检查等等。知道Border原理之后就有一个很简单的方法：判断每个节点的值是否为0，是则是符合题意的字符串。

原因很简单，一个回文串有长的回文后缀，意味着这个后缀在第一阶等差数列上，倘若不在，就找到第二阶梯第一个字符串，上个字符串为和上上个为，那么按照定理5，有，又，因此，这是不可能的。

既然第一阶等差数列上，那么自然有是的倍数。因此满足条件的回文串至少一定满足这个倍数式子。满足式子的回文串，当然也是满足条件的：因为由定理4或者定理6，满足倍数的后缀一定是回文串。

类似的问题还有洛谷4287 双倍回文。当然，由于那道题求的不是个数，而是最大长度，因此用Manacher算法也可以做。

Codeforces932 G

这题应该相当经典了。可以说是万恶之源（雾。

首先我们发现，如果构造字符串，那么问题会变成将字符串最少划分为多少个长度为偶数的字符串。

普通的方法很显然，就是沿着回文自动机失配边走。但是每个节点走完，次数的和是可以达到级别的，（比如：aaa...aa)。这里需要优化。

以下说明同样参考自博客：https://xlor.cn/2019/11/mpf/

回文树上的需要多维护两个信息和 。 前者表示节点和最长回文后缀的长度之差，即 。 后者表示节点一直沿着 fail 向上跳到第一个节点 ，使得，也就是

所在等差数列中长度最小的那个节点。

根据上面证明的结论，如果使用 指针向上跳的话，每向后填加一个字符，只需要向上跳次。因此，可以考虑将一个等差数列表示的所有回文串的 值之和，记录到最长的那一个回文串对应节点上。

图片.png

假设当前枚举到第 个字符，回文树上对应节点为 。 为橙色三个位置的值之和（最短的回文串 算在下一个等差数列中）。 上一次出现位置是 （在 处结束）， 包含的 值是蓝色位置。因此，实际上等于 和多出来一个位置的值之和，多出来的位置是。最后再用去更新，这部分等差数列的贡献就计算完毕了，不断跳，重复这个过程即可。

参考代码：

#include <cstdio>
#include <cstring>

#define mo 1000000007

using namespace std;

namespace PAM {
    const int N = 1000005, M = 26;
    int T[N][M], fail[N], len[N], sz, last, slink[N], dif[N];
    char s[N];

    void init() {
        len[0] = 0, len[1] = -1;
        sz = 1, last = 0;
        fail[0] = 1;
        memset(T[0], 0, sizeof(T[0]));
        memset(T[1], 0, sizeof(T[1]));
    }

    int get(int j, int pos) {
        while (pos == len[j] || s[pos - len[j] - 1] != s[pos])
            j = fail[j];
        return j;
    }

    void add(int c, int pos) {
        int t = get(last, pos);
        if (!T[t][c]) {
            len[++sz] = len[t] + 2;
            fail[sz] = T[get(fail[t], pos)][c];
            T[t][c] = sz;
            memset(T[sz], 0, sizeof(T[sz]));
            dif[sz] = len[sz] - len[fail[sz]];
            slink[sz] = dif[sz] == dif[fail[sz]] ? slink[fail[sz]] : fail[sz];
        }
        last = T[t][c];
    }
}

using namespace PAM;

char t[N];
int n, dp[N], g[N];

int main() {
    scanf("%s", t);
    n = strlen(t);
    if (n & 1) {
        putchar('0');
        return 0;
    }
    for (int i = 0, j = 0; i < n >> 1; i++)
        s[j++] = t[i], s[j++] = t[n - i - 1];
    init();
    for (int i = 0; i < n; i++) {
        add(s[i] - 'a', i);
        for (int j = last, np; j > 0; j = slink[j]) {
            np = i - len[slink[j]] - dif[j];  //np最小为-1
            g[j] = np >= 0 ? dp[np] : 1;
            if (dif[j] == dif[fail[j]])
                g[j] = (g[j] + g[fail[j]]) % mo;
            if (i & 1)  //注意回文串必须是偶数，所以对应i%2==1
                dp[i] = (dp[i] + g[j]) % mo;
        }
    }
    printf("%d", dp[n - 1]);
    return 0;
}