String

自动关联目录:String

字符串问题的三个层次:

  1. 单串:在一个串里找结构(回文、周期、子串)
  2. 双串:两个串的关系(匹配、最长公共子串/子序列)
  3. 多串:一堆串的查询(Trie、AC 自动机、后缀数组)

字符串匹配

在文本TT(长nn)中找模式串PP(长mm)出现的位置。

暴力

for (int i = 0; i + m <= n; i++) {
    bool ok = true;
    for (int j = 0; j < m; j++)
        if (T[i + j] != P[j]) { ok = false; break; }
    if (ok) /* 在 i 处匹配 */;
}

O(nm)O(nm)。最坏很慢,但实际数据下通常够快(因为常常很快就失配)。

KMP

核心思想:失配时不回退文本指针,利用模式串自身的重复结构跳到合适位置继续比。

前缀函数(next / failure 数组)

π[i]=子串 P[0..i] 的最长的"相等的真前缀和真后缀"的长度\pi[i] = \text{子串 } P[0..i] \text{ 的最长的"相等的真前缀和真后缀"的长度}

P = "ababaca"
π = [0, 0, 1, 2, 3, 0, 1]

i=2: "aba"   最长相等前后缀 = "a"      长度 1
i=3: "abab"  = "ab"                    长度 2
i=4: "ababa" = "aba"                   长度 3
i=5: "ababac" 无                       长度 0

构造

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];   // 回退
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

O(n)O(n),每个字符最多被比较常数次。

匹配

vector<int> kmp(const string& T, const string& P) {
    vector<int> pi = prefix_function(P);
    vector<int> pos;
    int j = 0;
    for (int i = 0; i < (int)T.size(); i++) {
        while (j > 0 && T[i] != P[j]) j = pi[j - 1];
        if (T[i] == P[j]) j++;
        if (j == (int)P.size()) {
            pos.push_back(i - j + 1);      // 匹配起点
            j = pi[j - 1];                 // 继续找下一个(允许重叠)
        }
    }
    return pos;
}

复杂度:O(n+m)O(n + m)。

KMP 的其他用途

  • 求最短循环节:n−π[n−1]n - \pi[n-1](若n mod (n−π[n−1])==0n \bmod (n - \pi[n-1]) == 0,则该长度是最小周期)
  • 求所有 border(相等前后缀):沿π[n−1]→π[π[n−1]−1]→⋯\pi[n-1] \to \pi[\pi[n-1]-1] \to \cdots 走
  • 字符串最小表示法的一部分

Z 算法

z[i]=从 s[i] 开始的后缀与 s 本身的最长公共前缀长度z[i] = \text{从 } s[i] \text{ 开始的后缀与 } s \text{ 本身的最长公共前缀长度}

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;                    // 当前最右的匹配区间 [l, r)
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);     // 利用已有信息
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}

匹配:把P+#+TP + \text{\#} + T 拼起来算 Z 数组,z[i]==mz[i] == m 的位置就是匹配点。

Z 算法 vs KMP:都O(n+m)O(n+m)。Z 更好理解,KMP 更省空间(不需要拼接)。

字符串哈希

见哈希章节。O(n+m)O(n + m) 但有碰撞风险。

竞赛共识:能用 KMP/Z 就用,哈希只作为"够用就好"的替代方案。

对比

算法预处理匹配备注
暴力—O(nm)O(nm)实际常常够快
KMPO(m)O(m)O(n)O(n)经典,无碰撞
Z 算法O(n+m)O(n+m)—更好写
哈希O(n)O(n)O(n)O(n)有碰撞风险
后缀数组O(nlog⁡n)O(n\log n)O(mlog⁡n)O(m\log n)多串查询用

Trie(前缀树)

把一组字符串按前缀组织成树,用于快速查询"某个前缀是否存在""哪些串以某前缀开头"。

插入 "he", "she", "his", "hers"

        root
         │
         h ───── s
        / \       \
       e   i       h
      /     \       \
     *       s       e
    /         *       *
   r
  /
 s
 *
(* 表示单词结尾)
struct Trie {
    static const int N = 1e6 + 5, C = 26;
    int ch[N][C], cnt[N], tot = 0;

    Trie() { memset(ch, 0, sizeof ch); memset(cnt, 0, sizeof cnt); }

    void insert(const string& s) {
        int u = 0;
        for (char c : s) {
            int k = c - 'a';
            if (!ch[u][k]) ch[u][k] = ++tot;
            u = ch[u][k];
        }
        cnt[u]++;                      // 有几个串在此结尾
    }

    int query(const string& s) {       // s 作为完整串出现几次
        int u = 0;
        for (char c : s) {
            int k = c - 'a';
            if (!ch[u][k]) return 0;
            u = ch[u][k];
        }
        return cnt[u];
    }
};

复杂度:插入/查询O(∣s∣)O(|s|)。 空间:O(∑∣s∣×C)O(\sum |s| \times C)——这是主要缺点(字符集大时爆炸)。

变体:

  • 01 Trie:字符集是{0,1}\{0,1\},用于求最大异或值(贪心走相反的位)
  • 压缩 Trie / Radix Tree:把单链压缩,省空间
  • 持久化 Trie:支持历史版本查询

01 Trie 求最大异或对

// 对每个 x,在集合中找 y 使 x^y 最大
void insert(int x) {
    int u = 0;
    for (int i = 30; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (!ch[u][b]) ch[u][b] = ++tot;
        u = ch[u][b];
    }
}
int query(int x) {                 // 返回最大异或值
    int u = 0, res = 0;
    for (int i = 30; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (ch[u][b ^ 1]) {        // 走相反的位(贪心)
            res |= (1 << i);
            u = ch[u][b ^ 1];
        } else u = ch[u][b];
    }
    return res;
}

贪心正确性:异或值的高位优先,能取 1 就取 1(高位 1 比后面全 1 都大)。

AC 自动机(Aho-Corasick)

Trie + KMP 的 fail 指针——在文本中同时查找多个模式串。

结构:
  1. 所有模式串建成 Trie
  2. 每个节点加 fail 指针:指向"当前串的最长真后缀"对应的节点
     (和 KMP 的 π 数组完全对应)
  3. 匹配时沿 Trie 走,失配就跳 fail
struct AC {
    static const int N = 1e6 + 5, C = 26;
    int ch[N][C], fail[N], cnt[N], tot = 0;

    void insert(const string& s) {
        int u = 0;
        for (char c : s) { int k = c - 'a';
            if (!ch[u][k]) ch[u][k] = ++tot;
            u = ch[u][k]; }
        cnt[u]++;
    }

    void build() {
        queue<int> q;
        for (int k = 0; k < C; k++)
            if (ch[0][k]) q.push(ch[0][k]);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int k = 0; k < C; k++) {
                int v = ch[u][k];
                if (v) {
                    fail[v] = ch[fail[u]][k];      // 关键递推
                    q.push(v);
                } else {
                    ch[u][k] = ch[fail[u]][k];     // 补全转移(优化,省去跳 fail)
                }
            }
        }
    }

    int query(const string& T) {
        int u = 0, ans = 0;
        for (char c : T) {
            u = ch[u][c - 'a'];        // 因为补全了,直接走
            for (int t = u; t && cnt[t] != -1; t = fail[t]) {
                ans += cnt[t];
                cnt[t] = -1;           // 只计一次(可按需去掉)
            }
        }
        return ans;
    }
};

复杂度:建树O(∑∣s∣)O(\sum|s|),匹配O(∣T∣+匹配数)O(|T| + \text{匹配数})。

两个关键点:

  1. fail[v] = ch[fail[u]][k]:BFS 保证 fail[u] 已算好(层数更浅)
  2. 补全不存在的转移为 ch[fail[u]][k]:这样匹配时不用 while 跳 fail,直接一步走,快很多(以空间换时间)

应用:敏感词过滤、多模式匹配、结合 DP 做"不含某些串的字符串计数"。

回文

中心扩展法

// 以 i 为中心(奇数长度)和 i, i+1 之间(偶数长度)扩展
int expand(const string& s, int l, int r) {
    while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { l--; r++; }
    return r - l - 1;
}

int longestPalindrome(const string& s) {
    int best = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        best = max(best, expand(s, i, i));
        best = max(best, expand(s, i, i + 1));
    }
    return best;
}

O(n2)O(n^2),够用(n≤1000n \le 1000 时)。

Manacher 算法

O(n)O(n) 求每个位置为中心的最长回文半径。

// d1[i] = 以 i 为中心的奇数长度回文半径(含中心)
vector<int> manacher_odd(const string& s) {
    int n = s.size();
    vector<int> d1(n);
    int l = 0, r = -1;
    for (int i = 0; i < n; i++) {
        int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);   // 利用对称点
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
        d1[i] = k;
        if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
    }
    return d1;
}

核心技巧:维护当前最右的回文区间[l,r][l, r],若ii 在其中,利用它关于中心(l+r)/2(l+r)/2 的对称点l+r−il+r-i 的已知值作为初始值(mirroring),避免重复比较。

为什么是O(n)O(n):r 单调递增,每步的 while 循环要么推进 r(总共O(n)O(n) 次),要么不推进。

偶数长度:先做一次字符间插入分隔符(如 #)的转换,abc → #a#b#c#,统一成奇数。

后缀数组(Suffix Array)

把字符串所有后缀按字典序排序,得到排名数组 sa。

s = "banana"
后缀:
  "banana"    sa[0] = 5  "a"
  "anana"     sa[1] = 3  "ana"
  "nana"      sa[2] = 1  "anana"
  "ana"       sa[3] = 0  "banana"
  "na"        sa[4] = 4  "na"
  "a"         sa[5] = 2  "nana"

LCP 数组:lcp[i] = sa[i] 和 sa[i-1] 对应后缀的最长公共前缀。

构造(倍增法)

第 k 轮:按长度为 2^k 的子串排序
利用第 k-1 轮的排名,把 2^k 的子串看成两个 2^(k-1) 的排名对 → 基数排序 O(n)
共 log n 轮 → O(n log n)

应用:

  • 最长公共子串(两串拼接后求相邻后缀的 LCP 最大值)
  • 最长重复子串(lcp 数组的最大值)
  • 不同子串个数(n(n+1)/2−∑lcp[i]n(n+1)/2 - \sum lcp[i])
  • 模式匹配(二分 + LCP)

实现较复杂(O(nlog⁡n)O(n \log n) 倍增 + 基数排序约 60 行),实际竞赛里常用后缀自动机替代。

后缀自动机(SAM)

用O(n)O(n) 的空间表示字符串的所有子串,是一个最小的 DFA。

  • 状态数≤2n−1\le 2n-1,转移数≤3n−4\le 3n-4
  • 构造O(n)O(n),在线算法(逐字符添加)
  • 从根出发的任意路径对应一个子串

应用:

  • 不同子串个数
  • 最长公共子串
  • 子串出现次数
  • 字典序第 k 小子串

比后缀数组更强大但更难理解。入门建议先学后缀数组。

常见坑

  • KMP 的 pi 数组定义:是"最长相等真前后缀长度",不是"最长前缀"
  • KMP 匹配后 j = pi[j-1]:忘了这步就找不到重叠的匹配
  • Trie 的空间估算:N = 总字符数,别开小了
  • AC 自动机的 ch[u][k] = ch[fail[u]][k] 补全:不加会 TLE(每步都要跳 fail)
  • AC 自动机统计时重复计数:一个模式串出现在多个位置,或者沿 fail 链会重复。按需去重
  • 字符串哈希的碰撞:线上系统用哈希要先考虑攻击;竞赛里可能被卡
  • Manacher 的偶数长度:要么做两次,要么插入分隔符
  • 后缀数组的下标:sa[i] 是"排名第 i 的后缀的起始位置",rank[i] 是"从 i 开始的后缀的排名"。两个数组容易搞混
  • 字符集不是小写字母:用 map<char,int> 或扩大 C;但要注意空间
  • 中文/UTF-8:string 按字节索引会切断多字节字符。要先解码成 wchar_t 或用专门的库