数据结构复健(一):字符串算法

前缀函数与 KMP 算法

前缀函数

定义

对于一个长度为 $n$ 的字符串 $s$,其最大相等前后缀长度为 $k$ 当 \(s[0\cdots k-1]=s[n-k+1\cdots n]\) 且 $k$ 是满足这一条件的最大值。对于整个字符串,其前缀函数就是一个长度为 $n$ 的数组 $\pi[n]$,其中 $\pi[i]$ 的值为 $s[0\cdots i]$ 的最大相等前后缀长度。特别地,规定 $\pi[0]=0$

例如,字符串 \(abcdabcde\) 就有 \(\pi=\{0,0,0,0,1,2,3,4,0\}\)

前缀函数的计算

朴素算法

trivial $O(n^3)$

匹配优化

注意到相邻两项有 $\Delta\pi\le 1$,这是因为 于是可以在朴素算法的前提下进行优化,将 $\pi[n]$ 的枚举上界设为 $\pi[n-1]+1$,这样一来,容易证明时间复杂度为 $O(n^2)$。

失配优化

在上一个优化中,我们处理了 $\pi_{n+1}$ 的最优情况,即完成匹配,下面讨论无法完成匹配的情况,容易发现,下一个应该尝试的长度最大为 $\pi_{\pi_n - 1}$,这是因为其为满足 $s[0\cdots i-1]=s[n-i+1\cdots n]$ 的次大 $i$。

这样一来,我们就可以得到一个 $O(n)$ 的算法了。

实现

void prefix_funtion(std::string s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[j - 1];
        while (j && s[j] != s[i])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
}

应用

KMP 算法

过程

给定一个文本串 $t$ 与模式串 $s$,尝试找到 $s$ 在 $t$ 中的所有出现。

算法

考虑问题的本质:是否在 $t$ 中存在一段 $t[i\cdots i+n-1]$ 使得其与 $s$ 完全相等,显然,这可以转化为一个求前缀函数的问题,构造字符串 \(s+\#+t\) 其中 $#$ 代表一个无义分隔符。接下来,考虑在 $n+1$ 之后的区域考虑前缀函数,显然,找到匹配当且仅当 $\pi_i=n$。

求字符串的周期

若字符串内存在一个 $l$ 的周期,则显然其有一段长度为 $n-l$ 的相等前后缀。于是,根据求前缀函数的方式可以找到 $s$ 的最小周期,通过失配优化可以找到其所有周期。

统计每个前缀的出现次数

寻找 $s$ 的每一个前缀的出现次数,朴素方法是跑 $n$ 次 KMP,时间复杂度在平方量级,但是通过失配优化,很容易变成线性。

字符串压缩

与字符串周期是类同的,证明比较烦。

字符串哈希

定义

把字符串映射为一个整数,注意时间复杂度与 Hash 的准确率(避免 Hash 碰撞)。

应用

字符串匹配

求文本串每个字串的哈希值,与模式串直接比较即可。

允许 k 次失配的字符串匹配

匹配时允许至多有 $k$ 个位置上的字符不同($k$ 较小)。考虑哈希+二分,可以在每一次匹配过程中用 $O(\log n)$ 的时间找到所有失配字符,总时间复杂度为 $O(km\log n)$。

最长回文子串

枚举回文中心+二分,$O(n\log n)$,好像 $O(n)$ 哈希也可以,先咕。

AC 自动机

什么是自动机?

自动机的本质是一个状态转移函数 \(\delta(v, c)\) 其中 $v$ 代表一个状态,$c$ 代表一个新输入的字符。这个函数的输出结果是一个新的状态,也即:一个自动机在接受一个字符后由一种状态切换到另一种状态。有一些熟知的例子:

  1. Trie 树:接受一个字符后,向下沿着树边走到一个子节点;
  2. KMP 自动机:接受一个字符后,若匹配,将状态变为 $v+1$,若失配,变为 $\delta(\pi(i),c)$。

而 AC 自动机就是上面两者的结合。

用途

一个文本串,多个模式串进行匹配

失配优化

核心是在 Trie 树上跑失配指针。例如,对于字符串 abcd,bce,cf 构成的 Trie 树,若读入 abc 后在 d 处失配,将会把指针跳到 bce 字符串的 bc 后进行匹配,若再次失配,将跳到 cf 的 f 后进行匹配,依此类推。

实现

首先是建立失配指针的过程

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (tr[0][i])
            q.push(tr[0][i]);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) {
            if (tr[u][i]) { // 子节点存在,让 fail 指针指向父节点(拓扑序保证父节点 fail 指针的最优性)
                fail[tr[u][i]] = tr[fail[u]][i];
                q.push(tr[i][i]);
            } else { // 子节点不存在,直接跳转
                tr[u][i] = tr[fail[u]][i];
            }
        }
    }
}

接下来,进行匹配时,只需要不断跳指针即可

int e[MAXN]; // e[i] 表示以 i 结尾的模式串个数
int query(std::string t) {
    int u = 0, ans = 0;
    for (auto ch: t) {
        u = tr[u][ch - 'a']; // 一步到位跳到失配节点
        for (int j = u; j && e[j] != -1; j = fail[j]) {
            ans += e[j]; // 把每一个匹配都记录
            e[j] = -1; // 已经匹配到了
        }
    }
    return ans;
}



Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • OI 退役日记 (fake)
  • 「题解 P2282」HNOI2003 历史年份
  • 「题解 P6830」IOI2020 连接擎天树
  • 「题解 P7098」yLOI2020 凉凉
  • 基于 antlr4 的 Python 解释器