回文自动机

前言

给定一个字符串。保证每个字符为小写字母。对于的每个位置，请求出以该位置结尾的回文子串个数。

强制在线。需要算出后才能解密。

如果使用暴力做法，甚至 Manacher，时间复杂度肯定会至少。

所以，我们需要用另外一种方法来维护目前所有的回文字符串。使用即将要讲的回文自动机可以解决。

回文自动机（PAM）

他是一个自动机，维护了所有的不同的回文串。因为一个字符串的本质不同的回文子串最多只有个，所以最多个节点。

（：考虑在原字符串后新加一个字母。若本质不同的回文串增加了，那么肯定是目前以其结尾的最长的回文串。因为假设中间依然存在回文字符串，那么根据回文串左右对称，那么在就一定有一个字符串和完全相等。所以最多只增加 1 个。）

并且一些点与点中间连了一些转移边（有向边），代表在某个回文串的两端添加字母可以得到另一个回文串。

而且，也像其它自动机一样，每一个节点都存在一个回跳边（即 nxt 或 fail 边）。这些回跳边表示如果跑自动机到某一个节点，没有一条边匹配，就要跳最长回文 border 然后继续试配。

（这里定义最长回文 border 为一个字符串的最长为回文串的公共前后缀）

如何构造

一个 PAM 由一个回文 Trie 和一棵 Fail 树组成。每一个点要维护这个点表示的回文串的长度。设其为。

而因为回文有两种情况：回文中心为字母，即长度为奇数的串；回文中心为空，即长度为偶数的串。所以我们要设两个根。

一个根编号 0，令其，代表以这个点为根的子树里存的全是长度为偶数的回文串。另一个根编号 1，令其。代表以这个点为根的子树里面存的全是长度为奇数的回文串。设为的原因是，因为两端加同一个字母会使长度，这样就可以使长度变为，即一个字母的回文串了。然后使。

int tr[N][26], fail[N], len[N], cnt[N];
int idxcnt, pre;
void init(){
    fail[0] = 1, len[1] = -1;
    idxcnt = 1;
}

然后开始插入一个字母。我们定一个指针，代表在插入这个数之前跑到了 PAM 上的哪一个节点。

我们先定一个函数，代表在加入位置时，最长的、合法的回文后缀应该是多少。即跳 Fail 操作。因为我们知道，Fail 树维护的是一个回文串的最长回文 border 长度，所以我们就跳 Fail 树直到存在一个回文串它的左边的字符也是为止。

举个例子，假设现在的字符串为 aaaxxxcccxabacaba，目前以最后一个字符结尾的最长回文串为 abacaba。现在新插入一个字符 c，那么首先，不存在给字符串 abacaba 同时加上 c 的字符串，那么跳 Fail。然后最长回文 border 就是 aba。然后存在给 aba 同时加上 c 的字符串，为 cabac。那么就返回字符串 aba 代表的节点。若跳到 0 了还没有，没事，再跳一层就是 1，即的节点。它代表如果你要在它的两端加上 c，那么操作后的字符串就是 c 而不是 cc 了。

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

现在插入一个字母，那么就先求出的最长合法后缀回文串，用函数求出。设其代表的节点为。

若存在的一条边，就直接跳那条边，将设为它即可。

否则就要新建节点。步骤如下：

首先建边。将赋值为一个新 idx。
然后求出新节点的 Fail。因为要与这个节点不同，所以就要求。然后设新节点的 Fail 为即可。
最后修改为。然后设为这个新 idx 即可。

void insert(int alp, int pos){
    pre = getfail(pre, pos);
    if(tr[pre][alp] == 0){
        ++idxcnt;
        fail[idxcnt] = tr[getfail(fail[pre], pos)][alp];
        tr[pre][alp] = idxcnt;
        len[idxcnt] = len[pre] + 2;
    }
    pre = tr[pre][alp];
}

一个 PAM 就造好了！可以根据个人喜好封装。

例题

还是前言的那一道。首先插入这个字母。

查询以该位置结尾的回文子串个数就可以，再维护一个表示答案。因为“跳到这个节点”表示的是这个节点就是原本字符串的最长后缀回文串。所以求答案就只用求该节点的答案即可。在新建节点的时候，就可以设为其的即可。最后输出该节点的，解密即可。

P4762 Virus synthesis IN Lv.15

题目大意

初始有一个空串，利用下面的操作构造给定串。

1、串开头或末尾加一个字符

2、串开头或末尾加一个该串的逆串

求最小化操作数，，字符集为。

解答

首先，根据贪心，我们肯定要尽量的多使用操作 2。

那么，首先就给他建一个回文自动机。然后我们令为使建出节点代表的字符串所需花费最小步数。最开始初始化其为。

然后因为一个字符串想做一个操作 2 到达串，那么。那么我们就预处理为节点代表的字符串的最大长度的最长回文 border 代表的节点。这个东西可以先设初始值为它父亲的，然后一直跳直到小于，最后再走一条边即可。

然后，从点开始 BFS。因为做了一次操作 2 之后长度肯定是偶数。之后就算出每一个点的，然后再根据算出答案，取即可。