后缀系列 | SAM & SA

概述

OI 的字符串处理题目中,有很多题目需要用到后缀系列算法。在本文中,我将介绍几道使用 SAM 和 SA 性质求解的经典题目,并引入一些后缀系列算法的一些模型和套路。

SAM | 后缀自动机 Suffix Automaton

基本操作

  • void insert(int ch);:向 SAM 中追加一个字符 ch。

SAM 节点的意义 & 性质

每一个 SAM 节点都会记录一个深度(从起点开始走能走过的最长长度)和 link 指针。显然,每一条从起点出发,到达另外一个节点的路径都是字符串的一段子串。link 指针指向上一个可以接受该后缀的节点。有的时候我们需要建出 Link 树来进行 DP。

SAM 的经典问题解

子串是否存在

直接从 SAM 的跟节点开始走,如果无法继续走了,那么就说明不存在该子串。SAM 就是一个能识别字符串子串的自动机。

统计子串的信息

一般,统计子串的信息都是用 DP 来解决,比如说统计本质不同的子串个数或是子串总长度。利用 SAM 是 DAG 的特性,或是利用其 Link 树,都可以很好的进行 DP。(记得去除空串)

统计本质不同子串个数

例题:P2408

考虑子串在后缀自动机所对应的东西:根出发的路径。所以,这个问题可以被转换为在整个 DAG 中有多少条从根出发的不同路径。这个很好算,我就不再赘述。

统计本质不同的子串总长度

跟上一问差不多,把贡献改成路径长度即可。

统计一个子串出现的次数

一个字串在字符串中肯定有一个最早出现的地方,设置为节点\(u\)。发现其实就是搞定\(u\)节点的子树大小:因为他们都有相同的后缀。所以,树形 DP 一遍即可。

例题 A:CF1120C Compress String

这道题显然是一个 \(O(n^2)\) 的 DP。考虑设置状态\(f_i\)为到了第\(i\)为的最优代价。转移非常显然:

\[ f_i = \min \begin{cases} f_{i – 1} + A \\ f_j + b, \text{if } S[j + 1 \dots i] \subset S[1 \dots j] \end{cases} \]

考虑预处理出字串的最早节点\(pos[i][j]\)和每一个节点的最早出现位置,然后进行判断即可。

// CF1120C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

struct node
{
    int ch[26], link, dep, occur = 0x3f3f3f3f;
} nodes[MAX_N];

int n, ca, cb, ptot, last_cur, bucketA[MAX_N], bucketB[MAX_N];
int pos[5001][5001], dp[MAX_N];
char str[MAX_N];

void sam_initialize() { last_cur = ++ptot; }

void insert(int c, int pos)
{
    int cur = ++ptot;
    nodes[cur].dep = nodes[last_cur].dep + 1;
    nodes[cur].occur = pos;
    int p = last_cur;
    while (p && nodes[p].ch[c] == 0)
        nodes[p].ch[c] = cur, p = nodes[p].link;

    if (p == 0)
        nodes[cur].link = 1;
    else
    {
        int q = nodes[p].ch[c];

        if (nodes[p].dep + 1 == nodes[q].dep)
            nodes[cur].link = q;
        else
        {
            int clone = ++ptot;
            nodes[clone].dep = nodes[p].dep + 1;
            memcpy(nodes[clone].ch, nodes[q].ch, sizeof(nodes[q].ch));
            nodes[clone].link = nodes[q].link;
            while (p && nodes[p].ch[c] == q)
                nodes[p].ch[c] = clone, p = nodes[p].link;
            nodes[q].link = nodes[cur].link = clone;
        }
    }

    last_cur = cur;
}

void stringSort()
{
    for (int i = 1; i <= ptot; i++)
        bucketA[i] = 0;
    for (int i = 1; i <= ptot; i++)
        bucketA[nodes[i].dep]++;
    for (int i = 1; i <= ptot; i++)
        bucketA[i] += bucketA[i - 1];
    for (int i = 1; i <= ptot; i++)
        bucketB[bucketA[nodes[i].dep]--] = i;

    for (int i = ptot; i >= 1; i--)
        nodes[nodes[bucketB[i]].link].occur = min(nodes[nodes[bucketB[i]].link].occur, nodes[bucketB[i]].occur);
}

int main()
{
    sam_initialize();
    scanf("%d%d%d%s", &n, &ca, &cb, str + 1);
    for (int i = 1; i <= n; i++)
        insert(str[i] - 'a', i);
    for (int i = 1; i <= n; i++)
    {
        int p = 1;
        for (int j = i; j <= n; j++)
        {
            p = nodes[p].ch[str[j] - 'a'];
            pos[i][j] = p;
        }
    }

    stringSort();
    for (int i = 1; i <= n; i++)
    {
        dp[i] = dp[i - 1] + ca;
        for (int j = 1; j <= i - 1; j++)
            if (nodes[pos[j + 1][i]].occur <= j)
            {
                dp[i] = min(dp[i], dp[j] + cb);
                break;
            }
    }
    printf("%d", dp[n]);
    return 0;
}

SA | 后缀数组 Suffix Array

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注