字符串从基础到略微进阶算法学习笔记

· · 算法·理论

注意：我不太喜欢字符串哈希，所以我没有写。

注意：本文偏重于算法及其思想本身，涉及到的题目较少。

注意：本文中字符串下标从 0 开始。

注意：本文用 s[i: j] 表示字符串 s_i s_{i+1} s_{i+2} \cdots s_{j-1} s_{j}。

Trie 树（字典树）

我们要维护一个字符串的集合，比如 \{\texttt{long}, \texttt{longlong}, \texttt{lung}, \texttt{let}, \texttt{lulu}\}。我们当然可以直接存起来，但这样空间复杂度很不友好，同时查询时复杂度也比较大。

但我们发现它们有许多相同的前缀，所以我们可以想象出这样一个结构：

我们把一个字符当成一条边，一个字符串当成一个点。

它节约了许多空间，并且查询集合中是否存在或加入一个字符串的时候只要做一次 O(\mid S\mid) 的遍历就行了。

这就是 Trie 树，我们考虑实现它（假设只有小写字母）：

int n; // 树的大小

std::array<int, 26> nxt[N+5]; // 指向该节点的儿子节点 也可以用 vector

int flg[N+5]; // 该节点上是否存在一个字符串/存在多少字符串 比如上面的图中 flg[4]=1 flg[14]=0

void insert(std::string s) { // 向集合中加入一个字符串
    int pos(0);
    for(auto i : s) { // 遍历
        if(!nxt[pos][i-'a']) { // 没有就加入
            nxt[pos][i-'a']=++n;
            nxt[n].fill(0);
        }
        pos=nxt[pos][i-'a']; // 移动
    }
    flg[pos]++; // 加标记
}

bool insert(std::string s) { // 查询集合中是否存在一个字符串
    int pos(0);
    for(auto i : s) {
        if(!nxt[pos][i-'a']) return 0;
        pos=nxt[pos][i-'a'];
    }
    return flg[pos]!=0;
}

这是模板题：https://www.luogu.com.cn/problem/P8306，它要求查询前缀而非完整的字符串，也很简单：

void insert(std::string s) {
    int pos(0);
    for(auto i : s) {
        if(!nxt[pos][i-'a']) {
            nxt[pos][i-'a']=++n;
            nxt[n].fill(0);
        }
        pos=nxt[pos][i-'a'];
        flg[pos]++; // 在哪里都加标记
    }
}

这是另一道经典的题：https://www.luogu.com.cn/problem/P10471，看起来和字符串没有任何关系。但是我们可以把每个数字的二进制表示当成一个字符串，在遍历时从高位向低位贪心：

std::string find(std::string s) {
    int p(0);
    std::string ans;
    for(auto i : s) { // 每次如果有就取与当前位相反的那个
        if(i=='0') {
            if(nxt[p][1]) ans.push_back('1'), p=nxt[p][1];
            else ans.push_back('0'), p=nxt[p][0];
        } else {
            if(nxt[p][0]) ans.push_back('1'), p=nxt[p][0];
            else ans.push_back('0'), p=nxt[p][1];
        }
    }
    return ans;
}

我们把它称为 01 Trie 树。

动态开点线段树也是一种本质 01 Trie 树，并且 01 Trie 树可以当成平衡树用。

前缀函数和 KMP

有这样一个问题（单串匹配）：给定两个字符串 s 和 t，求出 t 在 s 中出现了几次。例如 s=\texttt{longanglong}, t=\texttt{ng}，那么 t 在 s 中出现了 3 次。

朴素的做法是遍历 s，判断从每个位置开始是否可行。但这样的时间复杂度是 O(\mid s\mid \mid t\mid) 的。

显然我们没有完全利用匹配时的信息，比如 t=\texttt{abcal}, s=\texttt{abcab}\cdots，它们的前 4 个字符相等，但第 5 个不同。在朴素算法中，此时我们应当尝试从 s 的第 2 个字符开始匹配，但这实际上是没有意义的。因为前 4 个字符中，t 的前缀 \texttt{a} 与后缀 \texttt{a} 相同，所以我们可以从 s 的第 4 个字符开始匹配。

但如何知道怎么跳跃呢？这里要用到前缀函数。

前缀函数

我们先来看一些定义：

真前缀：它是一个字符串 s 的前缀，但不是 s 本身。

border：如果对于一个字符串 s，它的一个长为 \ell 的真前缀与一个长为 \ell 的真后缀相等，这个前缀就是它的一个 border。

前缀函数：字符串 s 的前缀函数 \pi 是一个数组，其中 \pi_i 是 s[0: i-1] 的最长 border 的长度。如 s=\texttt{abcab} 的前缀函数是 \pi=[0, 0, 0, 1, 2]。

所以我们只要求出 t 的前缀函数即可。首先我们能想到这样一件事：如果 s_{\pi_i}=s_{i+1}，那么 \pi_{i+1}=\pi_{i}+1。如图：{\color{blue}\rule{5pt}{5pt}\rule{5pt}{5pt}}{\color{green}\rule{5pt}{5pt}}\rule{5pt}{5pt}\rule{5pt}{5pt}\rule{5pt}{5pt}{\color{blue}\rule{5pt}{5pt}\rule{5pt}{5pt}}{\color{green}\rule{5pt}{5pt}}，其中绿点为 s_{i+1} 和 s_{\pi_i}。

但如果 s_{\pi_i}\neq s_{i+1} 怎么办？我们可以考虑 \pi_{\pi_i-1}，它是 s[0: i-1] 的一个前缀的前缀，由 border 的定义，它也是一个相同的后缀的相同后缀，所以也满足上图形式。并且可以证明，它是 s[0: i-1] 的第二长的 border。

于是我们可以一直迭代求出前缀函数：

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

它的时间复杂度是 \Theta(n) 的，但是为什么？我们知道 j 增加的的总量不会超过 n，并且，j 总是不小于 0，所以 j 减少的的总量不超过 j 增加的的总量。而 while 循环总共迭代的次数不超过 j 减少的的总量，所以复杂度是线性的。

回到字符串匹配（Knuth–Morris–Pratt 算法）

于是我们可以写出字符串匹配的代码，也可以用均摊分析证明时间复杂度是 \Theta(n) 的：

std::vector<int> find(std::string s, std::string t) { // 这里返回出现的位置
    int n(s.length());
    int m(t.length());
    std::vector<int> loc(n). pi(next(t));
    for(int i(0), j(0); i<n; i++) {
        while(j>0 && t[j]!=s[i]) j=pi[j-1];
        if(s[j]==s[i]) j++;
        if(j==m) {
            loc.push_back(i-m+1);
            j=pi[j-1];
        }
    }
    return loc;
}

所以我为什么把求前缀函数的代码又写了一遍？

那有没有什么更无脑的方法呢？

有的，考虑字符串 f=t+\texttt{\#}+s，t 出现在满足 \pi_i=\mid t\mid 位置上（这里 \texttt{\#} 不能在 s 和 t 中出现）。

但是，不要用这种方法！就在短短一个暑假中，我就因为这种写法挂了两次，原因分别是：这种方法常数比一般的 KMP 大（TLE）；这种方法数组大小更大（RE）。

另一个应用

问题：有字符串 s，长度为 n，请求出它的最小周期，不要求完整。如 \texttt{abeabeabeabe} 的最小周期是 3，\texttt{abbdab} 的最小周期是 4。

一般的想法是枚举周期，用前缀函数判断是否合法，由调和级数的知识可知，它的复杂度是 \Theta(n\log n) 的。

然而周期的另一个定义是：若对于所有 i\in[0, n-p) 有 s_i=s_{i+p}，则 p 是 s 的一个周期。

更糟糕的是，这几乎就是在说 border。所以直接输出 n-\pi_{n-1}，复杂度为 \Theta(n)。

Z 函数

Z 函数与前缀函数恰恰相反，z_i 是 s 与 s[i: n-1] 的最长公共前缀的长度。

假设在求 z_i 前，前面元素的 Z 函数的最大值为 r，且 z_l=r，有下图：

如果 i+z_{i-l}\le r, i\le r，那么由 Z 函数定义，两个部分完全一样，z_i=z_{i-l}。

否则 z_i+i-1 一定在 r 右边，此时暴力向右尝试即可。因为每次扩展会使 r 向右移动一位，而 r\le n，所以时间复杂度是 \Theta(n) 的。

std::vector<int> z_function(std::string s) {
    int n(s.length());
    std::vector<int> z(n);
    z[0]=n;
    z[1]=0;
    while(z[1]<n && s[z[1]+1]==s[z[1]]) z[1]++;
    int l(1), r(z[1]);
    for(int i(1); i<n; i++) {
        if(i<=r) z[i]=std::min(r-i+1, z[i-l]);
        while(z[i]+i-1<n && s[z[i]+i]==s[z[i]]) z[i]++;
        if(z[i]+i-1>r) r=z[i]+i-1, l=i;
    }
    return z;
}

Z 函数的应用和前缀函数差不多，这里不提了。

Manacher 算法

这个可以不写吗。

Manacher 算法可以求字符串中以每个点为中点的回文串个数，因为回文串长度可能为偶数，所以考虑 s'=\texttt{\#}s_0\texttt{\#}s_1\texttt{\#}s_2\cdots\texttt{\#}s_{n-1}\texttt{\#}。

它使用了与 Z 函数类似的思想，使用 d_i 表示以 i 为中点的最长回文串长度，假设当前最长回文串的左右端点为 l, r，如果 i\le r，那么先令 d_i=\min(d_{r-l+i}, r-i+1)，然后暴力拓展即可，复杂度也是线性的。

（这个不知道放什么代码就不放了）

后缀数组（Suffix Array，SA）

后缀数组很有趣，应用也很广泛。

后缀数组可以把一个字符串的所有后缀按字典序排序，\text{sa}_i 表示字典序第 i 名的后缀的第一个字符在原串中的位置，\text{rk}_i 表示 s[i:n-1] 在后缀中的字典序排名。

例如：s=\texttt{ababa}，则 \text{sa}=[4, 2, 0, 3, 1]，\text{rk}=[0, 1, 2, 3, 4]。

下面我们来渐近地考虑后缀数组地求法。

O(n^2\log n)

首先考虑暴力，共有 \Theta(n^2) 个后缀，每次比较的时间复杂度是 O(n)，所以使用 std::sort 的时间复杂度是 O(n^2\log n)。

O(n\log^2n)

可以先换种思路，考虑基数排序，但时间复杂度还是 O(n^2\log n)。

但是后缀是有特殊性质的：后缀的后缀仍是后缀。所以假设比较 s[a: n-1] 和 s[b: n-1]，此时只考虑前 c 位的话 rk_a\le rk_b。

那我们只要比较 s[a+c: n-1] 和 s[b+c: n-1] 的字典序，也就是比较 rk_{a+c} 和 rk_{b+c} 就行了。而且这样一轮排序后，c 会翻倍。

所以时间复杂度成功变为 O(n\log^2 n)，已经可以做题了。

std::vector<int> suffix_array(std::string s) {
    int n(s.length());
    std::vector<int> sa(n), rk(n+1), nrk(n+1);
    rk[n]=-1;
    for(int i(0); i<n; i++) sa[i]=i, rk[i]=s[i]; // 按第一个字符排序
    for(int c(1); c<n; c<<=1) { // 倍增
        std::sort(sa.begin(), sa.end(), [&](int a, int b) {
            return rk[a]==rk[b]?rk[std::min(a+c, n)]<rk[std::min(b+c, n)]:rk[a]<rk[b];
        });
        nrk[sa[0]]=0;
        for(int i(1), k(0); i<n; i++) { // 这是为了保持稳定
            if(rk[std::min(sa[i]+c, n)]!=rk[std::min(sa[i-1]+c, n)] || rk[sa[i]]!=rk[sa[i-1]]) k++;
            nrk[sa[i]]=k;
        }
        for(int i(0); i<n; i++) rk[i]=nrk[i];
    }
    return sa;
}

\Theta(n\log n)

首先赞叹 std::sort 神力，但是 \text{rk} 的值域很小，可以用 LSD 基数排序做到单次排序 \Theta(n)。

非常可惜单 \log 跑得和双 \log 没什么区别。

std::vector<int> suffix_array(std::string s) {
    int n(s.length());
    std::vector<int> id(n), sa(n), rk(n+1), nrk(n+1), cnt(n+130+1);
    // 交替使用的 SA  新旧排名  计数排序用的桶
    rk[n]=0;
    for(int i(0); i<n; i++) sa[i]=i, rk[i]=s[i];
    for(int c(1); c<n; c<<=1) {
        // 处理 sa 使用计数+基数排序
        std::fill(cnt.begin(), cnt.end(), 0);
        for(int i(0); i<n; i++) cnt[rk[std::min(sa[i]+c, n)]]++;
        for(int i(1); i<=n+130; i++) cnt[i]+=cnt[i-1];
        for(int i(n-1); i>=0; i--) id[--cnt[rk[std::min(sa[i]+c, n)]]]=sa[i];

        std::fill(cnt.begin(), cnt.end(), 0);
        for(int i(0); i<n; i++) cnt[rk[id[i]]]++;
        for(int i(1); i<=n+130; i++) cnt[i]+=cnt[i-1];
        for(int i(n-1); i>=0; i--) sa[--cnt[rk[id[i]]]]=id[i];

        // 处理 rk
        nrk[sa[0]]=0;
        for(int i(1), k(0); i<n; i++) {
            if(rk[std::min(sa[i]+c, n)]!=rk[std::min(sa[i-1]+c, n)] || rk[sa[i]]!=rk[sa[i-1]]) k++;
            nrk[sa[i]]=k;
        }
        for(int i(0); i<n; i++) rk[i]=nrk[i];
    }
    return sa;
}

另外注意字符串长度可能比字符集大小小，开 cnt 数组的时候一定要开大一点。

另外后缀排序可以做到 O(n)，但显然不需要。

height 数组（Kasai 算法）

这是前缀数组一个强大的工具，能辅助解决一些问题。

首先有一个问题：给定一个字符串，多次询问两个后缀的最长公共前缀（lcp）的长度。

我们先考虑把所有后缀放到一个 Trie 树上，可以发现，问题就变为了求 LCA，而 LCA 可以转化为欧拉（DFS）序上的 RMQ。

另一个发现是 Trie 树上 DFS 序等价于字典序（应该是的）。

所以问题等价于后缀数组上的 RMQ，严格来讲后缀 s[l:n-1] 和 s[r:n-1] 的最长公共前缀长度为 \min_{i=l+1}^{r}\mid\operatorname{lcp}(s[i:n-1], s[i-1:n-1])\mid。于是我们定义 h_i=\mid\operatorname{lcp}(s[i:n-1], s[i-1:n-1])\mid。

一般来讲，这可以二分+哈希求，但是如果真要这么做，为什么不一开始就这么做呢？所以这里继续考虑线性做法。

事实上 h_{\text{rk}_i}\ge h_{\text{rk}_{i-1}}-1，虽然我觉得这很没道理。然后就可以做到线性了。

for(int i(0), k(0); i<n; i++) {
    if(!rk[i]) continue;
    if(k) k--;
    while(s[i+k]==s[sa[rk[i]-1]+k]) k++;
    h[rk[i]]=k;
}

其他说明

这篇文章中我没有写 AC 自动机，因为我太懒了，下次了。

很多内容参考了 yh 学长讲的课和 OI Wiki。