526互联

PAM学习笔记

发布时间 2023-07-10 18:42:50作者: crimson000

PAM

回文树（又称回文自动机 \(\texttt{PAM}\)），是一种可以高效解决大部分回文串问题的算法，在大部分情况下可以替代马拉车（当然模板题好像都替代不了），是一种不错的算法。

结构

trie

类似于其他的自动机（\(\texttt {AC}\) 自动机、\(\texttt{SAM}\)），\(\texttt{PAM}\) 也有一颗 \(\texttt{trie}\) 树以及相应的 \(\texttt{fail}\) 指针。但是不太相同的是，在 \(\texttt{PAM}\) 中，有两棵树（520 这天学这个正适合）。

555

为什么呢？因为回文串分为奇回文串和偶回文串，奇回文串当然可以直接插入，但是偶回文串就出现了问题。我们当然可以用类似马拉车的方法，添加不存在的字符来使它变成奇回文串，但是这样太麻烦了。于是我们可以建立两棵树，一颗奇树，一颗偶树，奇树的儿子都代表奇回文串，偶树的儿子都代表偶回文串。

下图是字符串为 \(\texttt{abaaabacca}\) 的回文树。

手绘不行请见谅

在这个字符串中，出现了以下这些回文串：

\[\texttt{a},\texttt{b},\texttt{c},\texttt{aba},\texttt{aaa},\texttt{cc},\texttt{acca},\texttt{baaab},\texttt{abaaaba} \]

我们可以注意到，在这个 trie 树上，一条转移边代表的是在字符串两边加上同一个字符，这也符合回文串的定义。

fail 指针

在 PAM 中，也拥有 fail 指针，且意义与 AC 自动机的相同，定义 \(fail[x]\) 为 \(x\) 代表的回文子串的最长回文后缀。

在 trie 树上，我们可以画出所有的 fail 指针。

红边为 fail（别吐槽画工了）

我们可以注意到，\(0\) 号点的 \(fail\) 指向了 \(-1\) 号点，这是因为奇根不可能失配（单个字符也是回文串）。

构建

在构建时，我们可以发现：如果我们要插入第 \(i\) 个位置的字符，它会和原字符串的末尾字符形成新的回文串。我们设这个最大回文串的长度为 \(len\)。

因为这个串是回文串，因此 \(s[i - len - 1\sim i]\) 为回文串，两边同时扣掉一个字符，我们就可以发现 \(s[i - len \sim i - 1]\) 也为回文串。因此我们只需要找一个最长的后缀回文串，满足 \(s[i - len - 1] = s[i]\)，我们就可以把这个字符插入到 \(s[i-len-1]\) 这个位置所代表的点后。

用图片描述就是：

如何找到这个最长的后缀呢？我们就可以利用 fail 指针。因为我们要找的都是后缀回文串，所以我们可以一直跳 fail，直到 \(s[i-len-1]\) 和 \(s[i]\) 相等为止。

而新建的这个点的 fail 指针也就可以指向匹配的点（这里也说不清楚），长度就是它父节点加二。

我们在构建时也可以求出一个十分常用的数组 trans，表示长度小于等于当前点的一半的最长回文后缀。

建树代码：

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

inline void build(int n)
{
    len[1] = -1, fail[0] = 1;
    idx = 1;
    for(int i = 1; i <= n; i ++ )
    {
        pos = getfail(cur, i);
        int u = s[i] - 'a';
        if(!tr[pos][u])
        {
            fail[++ idx] = tr[getfail(fail[pos], i)][u];
            tr[pos][u] = idx;
            len[idx] = len[pos] + 2;
            if(len[idx] <= 2) trans[idx] = fail[idx];
            else
            {
                int tmp = trans[cur];
                while(s[i - len[tmp] - 1] != s[i] || ((len[tmp] + 2) << 1) > len[idx])
                    tmp = fail[tmp];
                trans[idx] = tr[tmp][u];
            }
        }
        cur = tr[pos][u];
    }
}

例题

【模板】回文自动机（PAM）

作为模板题，还是比较简单的，统计答案只需要在 fail 指针的基础上加一即可。

for(int i = 1; i <= n; i ++ )
{
    s[i] = (s[i] - 97 + last) % 26 + 97;
    int pos = getfail(cur, i);
    if(!t[pos][s[i] - 'a'])
    {
        fail[++ idx] = t[getfail(fail[pos], i)][s[i] - 'a'];
        t[pos][s[i] - 'a'] = idx;
        len[idx] = len[pos] + 2;
        num[idx] = num[fail[idx]] + 1;
    }
    cur = t[pos][s[i] - 'a'];
    last = num[cur];
    printf("%d ", last);
}

P3649 [APIO2014] 回文串

本题需要我们统计回文串的出现次数，而当一个回文串出现时，它所对应的 fail 指针所对应的回文串也会出现一次，而它 fail 的 fail 也会出现。而我们如果每次都选择跳 fail，就会导致时间复杂度爆炸。

我们可以按照类似于AC自动机加强版的思路，因为我们插入字符串时是按照拓扑序，所以我们可以先在找到的点上打个标记，最后按照拓扑序向上统计答案即可。

inline void topsort()
{
    for(int i = idx; i >= 0; i -- ) cnt[fail[i]] += cnt[i];
}

for(int i = 0; i <= idx; i ++ ) ans = max(ans, (ll)len[i] * cnt[i]);

P4287 [SHOI2011]双倍回文

本题就用到了我们上面提到的 trans 数组。当一个点的 trans 指向的点的长度恰好为当前点长度的一半时，这个点即为一个双重回文串。

P4762 [CERC2014]Virus synthesis

因为进行一次 2 操作一定优于进行一次 1 操作，因此我们要尽可能的进行 2 操作。

我们设 \(f[i]\) 表示形成在 PAM 中编号为 \(i\) 的点所对应的回文串所需的最小操作次数。我们可以有如下转移：

  1. 在 PAM 上，我们设 \(x\) 扩展出 \(i\)，则当我们将 \(x\) 的一半加上一个字母，再翻折一下，就可以得到 \(i\) 对应的字符串。因此 \(f[i] = \min (f[x] + 1, f[i])\)。

  2. 设 \(trans_i = p\)，我们就可以得到下面的转移方程：\(f[i] = \min(f[i], f[p] + \frac{len_i}{2} - len_p + 1)\)。

最后统计答案，\(ans = \min \{ f[i] + n - len_i \}\)。

我们可以在 bfs 过程中进行状态的转移。

queue<int> q;
inline void bfs()
{
    while(q.size()) q.pop();
    q.push(0);
    while(q.size())
    {
        int u = q.front();
        q.pop();
        ans = min(ans, f[u] + n - len[u]);
        for(int i = 0; i < 4; i ++ )
        {
            int v = tr[u][i];
            if(!v) continue;
            f[v] = min(f[u] + 1, f[trans[v]] + len[v] / 2 - len[trans[v]] + 1);
            q.push(v);
        }
    }
}

Palindrome Partition

本题将字符串转换一下即可变为一个回文划分问题。

回文划分问题：将字符串 \(s\) 分成 \(k\) 段，使得 \(s_1, s_2 \cdots s_k\) 均为回文串。

在本题中，设 \(f_i\) 表示长度为 \(i\) 的前缀的划分方案。于是我们不难得出下面的转移方程：

设谓词 \(\mathrm{G(x)}\) 为 \(x\) 满足回文性质，则

\[f_i=\sum \limits _{\mathrm{G} (s[j+1\sim i])}f_j \]

这个转移的复杂度是 \(O(n^2)\) 的，我们考虑优化。

这里我们再引入两个信息：\(diff[u]\) 和 \(slink[u]\)。\(diff[u]\) 表示该节点和它的 \(fail\) 指针节点的长度差，即为 \(len[u] - len[fail[u]]\)。\(slink[u]\) 表示 \(u\) 节点一直沿着它的 \(fail\) 指针向上跳，一直跳到第一个满足 \(diff[x] \not\ne diff[u]\) 的 \(x\) 号点。可以证明，一个节点从 \(slink\) 开始跳，跳到根节点的次数不会超过 \(\log |s|\) 次。

我们就可以将每一段等差数列中的 \(f\) 值之和存到该等差数列的末端。记为 \(g\)。为了求出这个 \(g\)，我们可以看下图：

来源：OIwiki

当前跳到了 \(x\) 号节点，我们将要求当前节点的 \(g[x]\)，我们可以看到，当前节点的 \(g[x]\) 只比 \(g[fail[x]]\) 多了一个值（蓝色为 \(g[x]\)，橙色为 \(g[fail[x]]\)），多出的位置为 \(i-len[slink[x]]-diff[x]\)（我也不会），我们就可以在跳 \(slink\) 的过程中不断更新 \(f\)。

代码：

void insert(int i)
{
    pos = getfail(cur, i);
    int u = s[i] - 'a';
    if(!tr[pos][u])
    {
        int x = New(len[pos] + 2);
        fail[x] = tr[getfail(fail[pos], i)][u];
        tr[pos][u] = x;
        diff[x] = len[x] - len[fail[x]];
        if(diff[x] == diff[fail[x]])
            slink[x] = slink[fail[x]];
        else slink[x] = fail[x];
    }
    cur = tr[pos][u];
}

void build(int n)
{
    init();
    f[0] = 1;
    for(int i = 1; i <= n; i ++ )
    {
        insert(i);
        for(int x = cur; x > 1; x = slink[x])
        {
            g[x] = f[i - len[slink[x]] - diff[x]];
            if(diff[x] == diff[fail[x]]) g[x] = add(g[x], g[fail[x]]);
            if((i & 1) == 0) f[i] = add(f[i], g[x]);
        }
    }
}