wiki - 算法小站

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

字符串

回文串

回文树

[[ item.c ]]

回文树

## 回文自动机
**节点**
节点树最多$$n$$个，每个节点代表一种回文串，用$$S(u)$$表示节点$$u$$代表的回文串
那么我们有$$len(u) = |S(u)|$$

**后继边**
每个后继边上有一个字符，用`trans(u, ch) = v`表示`u`这个节点有后继边`ch`指向`v`节点
有`S(v) = ch S(u) ch`，以及$$len(v) = len(u) + 2$$

**失配边**
每个节点有一个失配边，用`fail(u) = v`表示`u`节点的失配边指向`v`节点，那么有$$S(v)$$是$$S(u)$$的最大 Border
也就是最长回文后缀

**PAM的构造**
实际上是求每个前缀的最长回文后缀，方法是暴力$$i-1$$位置的回文后缀，即`fail链`
![](/media/content_img/PAMBuild.png)
从最长的链开始看，如果两端匹配不上，说明`当前的 Border`太长了，顺着`fail 链`，尝试让其短一些，看看能不能匹配上

**PAM的特殊之处**
对于奇回文串和偶回文串，需要有`2`个根节点
最短的偶回文串形如`aa`，最短的奇回文串形如`a`，一般来说，都有一个空节点$$\emptyset$$作为根节点
然后其他所有可能的回文串，都是可以从根节点沿着某条路径可达

那么问题来了，PAM 在构造的时候，`len[v] = len[u] + 2`，根节点的`len`设置成多少合适呢？
如果是`0`，那么奇数回文串该如何表示呢？

解决方法是，设`2`个根节点，**偶根长度为`0`，奇根长度为`-1`**
方便起见，偶根的**失配边**指向奇根，奇根的**失配边**指向偶根

**PAM构建算法**
![](/media/content_img/PAMBuild02.png)

注意到，如果沿着父亲的`fail`链，找能接上`ch`的点，它跳回了自身，说明没有 Border 能够接上`a`

![](/media/content_img/PAMBuild03.png)

在构造的时候，不一定每次都有新的节点产生，如果最大回文后缀已经出现过的话，那么直接指向已经存在的节点即可

#### 算法实现
**时间复杂度**
可以用**势能分析**
将势能定义为`len(last)`，每一次新建节点，`势能 += 2`，但我们需要爬`fail 链`
爬`fail 链`会让势能`-1`，但总的来看，每新建一个节点，势能`+2`，总的时间复杂度是$$O(2n)$$

**空间复杂度**
注意到`fail 边`至多有$$O(n)$$条，同时`trans() 边`也最多$$O(n)$$条
所以边的上界是$$O(2n)$$的

但是用朴素的存边方法，`trans(maxn, 26)`，最多会有$$26n$$条边
如果非要卡空间的话，用`map`维护`trans`数组，或者用哈希表，转移`trans[u][ch]`用二元组$$(u, ch)$$代替
哈希映射`(u, ch) --> hashv`，看一下`(u, ch)`这个节点是否存在，不存在才需要建出来

```bash
class PAM {
public:
    static constexpr int ALPHA_SZ = 26;
    struct Node {
        int len, fail;
        // 以这个节点结尾的回文子串的数量
        int cnt;
        // 同样的回文结构出现的次数
        // u 出现了 tot 次，u 的所有回文后缀也会出现 tot 次，看情况令 tot[fail[u]] += tot[u]
        int tot = 0;
        array<int, ALPHA_SZ> next;

Node() : len{}, fail{}, cnt{}, next{} {}
    };

vector<Node> tr;
    int last;
    string s;

PAM() {
        init();
    }

void init() {
        // s 1-indexed
        // 0 偶根，1 奇根
        tr.assign(2, Node());

tr[0].len = 0, tr[0].fail = 1;
        tr[1].len = -1, tr[1].fail = 0;
        last = 0;

s.clear();
        s.push_back(' ');
    }

int New() {
        tr.emplace_back();
        return tr.size() - 1;
    }

bool add(int idx, char c, char offset = 'a') {
        int pos = s.size();
        s += c;
        int ch = c - offset;
     
        auto getfail = [&](const int x) -> int {
            auto cur = x;
            while (true) {
                auto curlen = tr[cur].len;
                if (pos-1-curlen >= 1 && s[pos-1-curlen] == s[pos]) break;
                cur = tr[cur].fail;
            }
            return cur;
        };

int fa = getfail(last);

if (tr[fa].next[ch]) {
            last = tr[fa].next[ch];
            tr[last].tot += 1;
            return false;
        }

int num = New();
        last = num;
        tr[num].len = tr[fa].len + 2;
        tr[fa].next[ch] = num;

if (tr[num].len == 1) {
            // 若为单个字符，指向偶根
            // 1[-1] + ch, len = -1+2 = 1, fail = 0[1]，相互指针
            tr[num].fail = 0;
            tr[num].cnt = 1, tr[num].tot = 1;
            return true;
        }

auto y = getfail(tr[fa].fail);
        tr[num].fail = tr[y].next[ch];

tr[num].tot = 1;
        tr[num].cnt = tr[tr[num].fail].cnt + 1;

// 其他要做的事情
        if (tr[num].len % 4 == 0) {
            int halflen = tr[num].len / 2;
            int l1 = idx - tr[num].len + 1;
            int l2 = l1 + halflen;

// debug(make_pair(l1, l2));

if (hs.getpre(l1, l1 + halflen - 1) == hs.getpre(l2, l2 + halflen - 1)) {
                 chmax(res, tr[num].len);
            }
        }

return true;
    }
};
```
### 一些问题
#### 双倍回文
**[SHOI2011 双倍回文](https://ac.nowcoder.com/acm/contest/33548/E)**
给定一个字符串`S`，求最长的双倍回文子串，若一个串能表示成`[T R(T)] [T R(T)]`的形式
那么就是一个双倍回文串，比如`abba abba`，双倍回文串的长度，必须是`4`的倍数
回文一次还不够，要回文`2`次

**算法分析**
从回文自动机的角度来看，实际上就是要找到最长的回文串，满足**如下限制**
假设说找到了一个回文位置$$x$$，那么`[m...] + [c...R(c)]`是一个回文串
一整个串是回文，我们有`m = R(c)`，另一方面，一半是回文，我们有`c = R(c)`
从而`m = c = R(c)`，**回文后缀的长度恰好是整个回文串长度的一半**

枚举回文自动机上的所有点，这个点代表的回文串长度`len(x) = tr[x].len`，它要合法，当且仅当
1）`len(x) mod 4 = 0`
2）`x`存在一个回文后缀`pos`，使得`tr[pos].len * 2 = tr[x].len`
由于`x`的回文后缀就是跳`x 的 fail 链`，令`pos = x`，然后跳`pos = tr[pos].fail`
找到第一个满足`tr[pos].len * 2 <= tr[x].len`的位置，检查是否满足$$2len(pos) = len(x)$$
如果满足，那么`len(x)`就可以用来更新答案

#### 回文串
**[APIO2014 回文串](https://ac.nowcoder.com/acm/contest/33548/F)**
给定一个字符串`S`，定义`S`子串$$T$$的价值是$$F(T) = |T| \cdot cnt(T)$$
其中`cnt(T)`表示$$T$$在$$S$$中出现次数，求$$S$$价值最大的回文子串

**算法分析**
注意到，PAM 可以求出本质不同的回文子串，最多只有$$n$$个，`tot`数组维护了同样的回文结构在原串中出现的次数
比如`abacaba`，那么`aba`这个结构，出现在`{i = 3, i = 7}， tot = 2`
当一个节点被`last`指向的时候，这个节点的`tot`值就`+= 1`

注意到`[abacaba]`出现了`tot`次，它的**所有回文后缀**也都出现了`tot`次
那么这个节点，表示的所有回文串的出现次数，等于`fail 树`的子树的和

这你可以`dfs`，但会被卡常，实际上，**树等价于从根节点出发的 DAG**
在`DAG`上`dp`，转移是根据拓扑序，$$dp(i) \leftarrow dp(i - 1)$$
那么在`fail 树`上，**节点编号从大到小，就是一个天然的拓扑序**
```bash
for i = N downto 1
	tot[ fail[i] ] += tot[i]
```
这样就可以了

#### Colorful String
**[Colorful String](https://ac.nowcoder.com/acm/contest/33548/G)**
定义一个字符串的价值是，出现不同字母的个数
求 s 所有回文子串的价值之和

**算法分析**
出现的所有不同字母，可以用`26 位的二进制数`状态压缩`mask`来表示，每个节点额外维护一个`mask`
插入新字符的时候，`tr[u].mask = tr[fa].mask | (1<<'a')`即可

最后统计的时候，注意到 PAM 上一个节点代表一种回文结构，并且维护了这种回文结构出现次数`tot`
求$$\sum_u tot(u) \cdot popcnt(mask_u)$$即可

统计的时候，注意`tot[u]`并不是真正的出现次数，因为`u`出现了`tot 次`，那么`u`所有的**回文后缀**也会出现了`tot`次

需要沿着拓扑序，`tot[ fail[u] ] += tot[u]`更新，才是每个节点真正出现的次数

## Palindrome Series
很多时候，求字符串分割的最优方案，会有形如以下式子的 dp
```math
dp(i) = \max(dp(i - P) + cost([i-p+1 \cdots i])), \quad \text{[i-p+1, i] 是回文后缀}
```
比如将$$S$$分割成若干回文串，使得`cost`总代价最大
那么在上面的 dp 表达式中，你需要枚举$$i$$，同时还需要枚举所有可能的回文分割位置$$P$$
这样复杂度就是$$O(n^2)$$了

但是，**一个字符串的 Border 可以划分成$$O(\log n)$$段等差数列**，基于此，我们可以用类似树链剖分的方法来处理

```bash
len[i]，表示 PAM 节点代表的回文串的长度
fail[i]，表示节点的失配指针，即最长的回文后缀，也就是最大 border
diff[i] = len[i] - len[ fail[i] ]，表示一个节点和他的最大 border 长度的差，也就是所在等差数列的公差
top[i] 表示节点 i 所在的等差数列首项位置，即从 i 开始往上走，保证 diff 值都相同，最终走到的点（这里的点针对 PAM 而言的）

g[i] 维护每个点到链顶的信息，维护的范围是 (len[ top[i] ]...len[i] ]，公差是 d = diff[i]
注意到这里的范围不包括 len[ top[i] ]，维护的最小长度是 L = len[ top[i] ] + len[i]

f[i] 表示维护的信息，一般指方案数
```
一般来说，我们有$$g(i) = \sum\_{j \in diff} f(j)$$

**转移方法**
注意到`len, fail, top, diff`都可以在`PAM`构造的时候，在线转移，难点在于$$f, g$$的转移
![](/media/content_img/palindrome-Series.png)
![](/media/content_img/palindrome-Series02.png)

具体做的时候，需要一边 dp，一边维护 PAM 上对应的$$g(u)$$

**算法实现**
```bash
void trans(vector<i64> &dp, int i) {
	在 pam 中，枚举当前 last 对应的 log 段等差数列链
	
	for(int p = last; p >= 2; p = top(p))
		auto L = len(top(p)) + diff(p)
		g[p] = dp[i - L]，即扣除最后拼接的回文段，只尝试扣除最小的一段
		
		if diff[p] == diff[fail[p]]:		g[p] += g[fail[p]]
		
		dp[i] += g[p], 将每 log 段等差数列链的方案数，合并到 i 中
}
```

## Codeforces Round 463
### G
**[G. Palindrome Partition](https://codeforces.com/problemset/problem/932/G)**
给定一个字符串`s`，问有多少种方式将`s`划分成若干子串，使得分割后有$$k$$个连续子串
记为$$(p_1, p_2, \cdots, p_k)$$，对所有的$$1 \leqslant i \leqslant k$$，均有$$p(i) = p(k-i+1)$$
保证$$k$$是偶数，方案数很大，对`1e9 + 7`取模

**算法分析**
题中给出的串的形式如下
```math
\displaystyle
[x_1x_2\cdots x_{m-1}x_m] \cdots [x_1x_2\cdots x_{m-1}x_m]
```
这样我们是没有办法`dp`的，因为问的是**方案数**，可以考虑等价转换
**首尾配对**，可以得到串
```math
\displaystyle
T = x_1x_m \ x_2x_{m-1}  \cdots x_{m-1}x_2 \ x_mx_1
```
因此可以奇数位放正序的串，偶数位错开放逆序的串，原问题的方案数，等价于
将$$T$$分割成若干回文子串的方案数，可以求出状态转移方程
```math
\displaystyle
dp(i) = \sum_j dp(j) , \quad [j+1\cdots i] \text{ 是回文串} \\
\text{同时, i 是偶数}
```

**算法实现-PAM 部分**
```bash
class PAM {
public:
    bool add(int idx, char c, char offset = 'a') {
        int pos = s.size();
        s += c;
        int ch = c - offset;
     
        auto getfail = [&](const int x) -> int {
            auto cur = x;
            while (true) {
                auto curlen = tr[cur].len;
                if (pos-1-curlen >= 1 && s[pos-1-curlen] == s[pos]) break;
                cur = tr[cur].fail;
            }
            return cur;
        };

int fa = getfail(last);

if (tr[fa].next[ch]) {
            last = tr[fa].next[ch];
            tr[last].tot += 1;
            return false;
        }

int num = New();
        last = num;
        tr[num].len = tr[fa].len + 2;
        tr[fa].next[ch] = num;

auto updDiff = [&]() -> void {
            tr[num].diff = tr[num].len - tr[tr[num].fail].len;
            tr[num].top = (tr[num].diff == tr[tr[num].fail].diff) ? tr[tr[num].fail].top : tr[num].fail;
        };

if (tr[num].len == 1) {
            // 若为单个字符，指向偶根
            // 0[-1] + ch, len = -1+2 = 1, fail = 1[0]，相互指针
            tr[num].fail = 1;
            tr[num].cnt = 1, tr[num].tot = 1;

updDiff();
            return true;
        }

auto y = getfail(tr[fa].fail);
        tr[num].fail = tr[y].next[ch];

tr[num].tot = 1;
        tr[num].cnt = tr[tr[num].fail].cnt + 1;
        updDiff();

// 其他要做的事情

return true;
    }
	
	// dp 转移，将一整个等差数列链的 dp 之和，用 g 维护起来
	void trans(vector<mint> &dp, int i) {
        for (int p = last; p >= 2; p = tr[p].top) {
            auto L = tr[ tr[p].top ].len + tr[p].diff;

tr[p].g = dp[i - L];
            if (tr[p].diff == tr[tr[p].fail].diff) tr[p].g += tr[tr[p].fail].g;

if (i % 2 == 0) dp[i] += tr[p].g;
        }
    }
};
```
**算法实现-dp 部分**
```bash
void solve() {
    PAM pam;
    vector<mint> dp(n+5, 0);
    dp[0] = 1;

for (int i = 1; i <= n; i++) {
        pam.add(i, T[i]);
        pam.trans(dp, i);
    }

auto ans = dp[n];
    cout << ans << "\n";
}
```
## 2019 ICPC 沈阳 M
**[2019 ICPC 沈阳 M](https://ac.nowcoder.com/acm/contest/33548/J)**
给定一个串$$S$$，要求在$$S$$中选出`3`个互不相交的回文子串，求长度之和的最大值

**算法分析**
思路比较直接的`dp`，其中$$dp(i, k)$$表示前$$i$$个位置，选出$$k$$个不相交的回文子串，构成的最大长度
那么转移，就是根据$$i$$这个位置选或者不选来

如果不选$$i$$，那么$$dp(i, k) = dp(i-1, k)$$
如果选$$i$$
若$$k = 1$$，那么就必须是以$$i$$结尾的最长回文后缀，找到它在 PAM 上对应的点$$u$$
我们有$$dp(i, 1) = len(u)$$

否则的话，**枚举回文后缀**，$$[j+1\cdots i]$$构成回文后缀，存在转移
```math
\displaystyle
dp(i, k) = \max_{1 \leqslant j < i} (dp(j, k-1) + i - j) = (\max_j dp(j, k-1) - j) + i
```
这个问题和上面的问题大同小异，之前是维护**等差数列段的和**，现在改成
维护等差数列段$$dp(j, k-1) - j$$的 max，节点上维护$$g(u, k)$$`= tr[u].g[k]`

**算法实现**

```bash
class PAM {
public:
    void trans(vector<vector<int> > &dp, int i) {
        for (int k = 0; k < K; k++) chmax(dp[i][k], dp[i-1][k]);

for (int k = 0; k < K; k++) {
            for (int p = last; p >= 2; p = tr[p].top) {
                auto L = tr[ tr[p].top ].len + tr[p].diff;
                auto j = i - L;

tr[p].g[k] = dp[j][k] - j;
                if (tr[p].diff == tr[tr[p].fail].diff) chmax(tr[p].g[k], tr[tr[p].fail].g[k]);

if (k == 0) chmax(dp[i][k], tr[p].len);
                else chmax(dp[i][k], tr[p].g[k-1] + i);
            }
        }
    }
}
```

看完文章有啥想法

算法小站

wiki 主题

字符串

回文树

目录