罗罗编程学习记录
本页内容 展开查看

02.12.4 字符串进阶

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.12 图与字符串进阶

覆盖范围

  • AC 自动机多模式匹配
  • 后缀数组
  • Manacher 最长回文
  • 字符串哈希

高频题速览

编号 题目 难度 频率
02.12.4-001 AC 自动机多模式匹配 高级 ★★★
02.12.4-002 AC 自动机构建 fail 指针 高级 ★★★
02.12.4-003 后缀数组 SA 原理 高级 ★★
02.12.4-004 Manacher 最长回文 进阶 ★★★★
02.12.4-005 KMP 回顾与边界 基础 ★★★★
02.12.4-006 字符串哈希 基础 ★★★★
02.12.4-007 AC 自动机 vs Trie 基础 ★★★
02.12.4-008 各算法复杂度对比 基础 ★★★

02.12.4-001 AC 自动机多模式匹配

频率 ★★★ | 难度 高级

一句话结论

AC 自动机在 Trie 上建 fail 指针(类似 KMP 的 next),用于多模式匹配;文本扫描时失配自动跳到最长可匹配后缀;时间 O(n + m + z),n 为文本长,m 为模式串总长,z 为匹配次数。

概念解释

  • Trie:所有模式串构建字典树。
  • fail 指针:失配时跳到的节点,类似 KMP next。
  • 多模式:一次扫描匹配所有模式串。

原理流程

  1. 构建 Trie。
  2. BFS 构建 fail 指针:根的子节点 fail 指向根;其他节点 fail = fail[父节点] 的子节点(同字符)。
  3. 扫描文本:从根出发,沿文本字符走;失配则跳 fail;走到终止节点则匹配。

代码 / 示例

class ACNode {
    ACNode[] children = new ACNode[26];
    ACNode fail;
    boolean isEnd;
    String word;
}
class AhoCorasick {
    private final ACNode root = new ACNode();

    void insert(String word) {
        ACNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) node.children[idx] = new ACNode();
            node = node.children[idx];
        }
        node.isEnd = true;
        node.word = word;
    }
    void buildFail() {
        java.util.Queue<ACNode> q = new java.util.ArrayDeque<>();
        root.fail = root;
        for (ACNode child : root.children) {
            if (child != null) { child.fail = root; q.offer(child); }
        }
        while (!q.isEmpty()) {
            ACNode u = q.poll();
            for (int i = 0; i < 26; i++) {
                ACNode v = u.children[i];
                if (v != null) {
                    ACNode f = u.fail;
                    while (f != root && f.children[i] == null) f = f.fail;
                    v.fail = (f.children[i] != null && f.children[i] != v) ? f.children[i] : root;
                    q.offer(v);
                }
            }
        }
    }
    java.util.List<String> search(String text) {
        java.util.List<String> result = new java.util.ArrayList<>();
        ACNode node = root;
        for (char c : text.toCharArray()) {
            int idx = c - 'a';
            while (node != root && node.children[idx] == null) node = node.fail;
            if (node.children[idx] != null) node = node.children[idx];
            ACNode tmp = node;
            while (tmp != root) {
                if (tmp.isEnd) result.add(tmp.word);
                tmp = tmp.fail;
            }
        }
        return result;
    }
}

常见误区

  • 误区:fail 指针构建用 DFS;正解:用 BFS,保证父节点 fail 先构建。
  • 误区:扫描时不跳 fail;正解:失配时必须跳 fail,才能匹配所有模式串。

追问 / 延伸

  • Q:时间复杂度? A:O(n + m + z)。
  • Q:AC 自动机用于什么? A:敏感词过滤、多模式匹配。

02.12.4-002 AC 自动机构建 fail 指针

频率 ★★★ | 难度 高级

一句话结论

fail[u] 表示 u 的最长可匹配后缀对应的 Trie 节点;BFS 构建:u 的子节点 v 的 fail = fail[u] 的同字符子节点(若不存在则继续跳 fail)。

概念解释

  • fail[u]:u 的最长可匹配后缀。
  • BFS 构建:按层构建,父节点 fail 先构建。
  • 类似 KMP:fail 指针类似 next 数组。

原理流程

  1. 根的子节点 fail 指向根。
  2. BFS u:
  3. 对 u 的子节点 v(字符 c):
  4. f = fail[u]。
  5. while f != root 且 f.children[c] == null:f = f.fail。
  6. v.fail = f.children[c] != null ? f.children[c] : root。

代码 / 图示

fail[u] = u 的最长可匹配后缀
BFS 构建:
  v = u.children[c]
  f = fail[u]
  while f != root && f.children[c] == null: f = f.fail
  v.fail = f.children[c] != null ? f.children[c] : root

常见误区

  • 误区:fail 构建用 DFS;正解:用 BFS。
  • 误区:根的 fail 指向 null;正解:根的 fail 指向自己。

追问 / 延伸

  • Q:fail 指针和 KMP next 区别? A:KMP next 是单模式,AC fail 是多模式(Trie 上)。
  • Q:fail 指针链优化? A:可以把 fail 路径压缩,减少扫描时跳转。

02.12.4-003 后缀数组 SA 原理

频率 ★★ | 难度 高级

一句话结论

后缀数组 SA[i] 表示排第 i 的后缀的起始位置;rank[i] 表示后缀 i 的排名;height[i] 表示 SA[i] 和 SA[i-1] 的最长公共前缀;用倍增法 O(n log n) 构建。

概念解释

  • SA[i]:排第 i 的后缀起始位置。
  • rank[i]:后缀 i 的排名。
  • height[i]:SA[i] 和 SA[i-1] 的 LCP。
  • 倍增法:O(n log n) 构建。

原理流程

  1. 初始排名 = 字符。
  2. 倍增:每次按前 2^k 个字符排名,基数排序。
  3. 直到所有排名不同。

代码 / 图示

SA[i]:排第 i 的后缀起始位置
rank[i]:后缀 i 的排名
height[i]:SA[i] 和 SA[i-1] 的 LCP

常见误区

  • 误区:SA 用快排;正解:快排 O(n^2 log n),倍增法 O(n log n)。
  • 误区:height 直接计算;正解:height 用 O(n) 递推。

追问 / 延伸

  • Q:SA 用于什么? A:最长重复子串、最长公共子串、后缀匹配。
  • Q:时间复杂度? A:倍增法 O(n log n)。

02.12.4-004 Manacher 最长回文

频率 ★★★★ | 难度 进阶

一句话结论

Manacher 在每个字符间插特殊字符(如 #),统一奇偶;用 p[i] 记录以 i 为中心的回文半径;利用对称性避免重复计算,O(n) 求最长回文。

概念解释

  • 插入 #:统一奇偶回文。
  • p[i]:以 i 为中心的回文半径。
  • 对称性:利用已知回文,减少重复计算。

原理流程

  1. 插入 #:s = "^#a#b#b#a#$"。
  2. 维护右边界 R 和中心 C。
  3. i 在 R 内:p[i] = min(p[2*C-i], R-i)。
  4. 中心扩展:i 为中心扩展回文。
  5. 更新 R 和 C。

代码 / 示例

String longestPalindrome(String s) {
    StringBuilder t = new StringBuilder("^#");
    for (char c : s.toCharArray()) t.append(c).append('#');
    t.append('$');
    int n = t.length();
    int[] p = new int[n];
    int C = 0, R = 0;
    for (int i = 1; i < n - 1; i++) {
        if (i < R) p[i] = Math.min(R - i, p[2 * C - i]);
        while (t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) p[i]++;
        if (i + p[i] > R) { C = i; R = i + p[i]; }
    }
    int maxLen = 0, center = 0;
    for (int i = 0; i < n; i++) if (p[i] > maxLen) { maxLen = p[i]; center = i; }
    return s.substring((center - maxLen) / 2, (center + maxLen) / 2);
}

常见误区

  • 误区:不插入 #;正解:插入 # 统一奇偶回文。
  • 误区:p[i] 初始为 0 不利用对称性;正解:i 在 R 内时 p[i] = min(R-i, p[2*C-i])。

追问 / 延伸

  • Q:时间复杂度? A:O(n)。
  • Q:Manacher vs 中心扩展? A:中心扩展 O(n^2),Manacher O(n)。

02.12.4-005 KMP 回顾与边界

频率 ★★★★ | 难度 基础

一句话结论

KMP 用 next 数组(前缀函数),失配时跳到 next 位置而不是从头开始;next[i] 表示模式串前 i 个字符的最长相等前后缀长度;时间 O(n+m)。

概念解释

  • next[i]:前 i 个字符的最长相等前后缀长度。
  • 失配:j = next[j-1],不是 j = 0。
  • 时间:O(n+m)。

原理流程

  1. 构建 next 数组。
  2. 匹配:i 遍历文本,j 遍历模式串;失配时 j = next[j-1]。

代码 / 示例

int[] buildNext(String p) {
    int[] next = new int[p.length()];
    for (int i = 1, j = 0; i < p.length(); i++) {
        while (j > 0 && p.charAt(i) != p.charAt(j)) j = next[j - 1];
        if (p.charAt(i) == p.charAt(j)) j++;
        next[i] = j;
    }
    return next;
}
int kmp(String text, String pattern) {
    int[] next = buildNext(pattern);
    int j = 0;
    for (int i = 0; i < text.length(); i++) {
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) j = next[j - 1];
        if (text.charAt(i) == pattern.charAt(j)) j++;
        if (j == pattern.length()) return i - j + 1;
    }
    return -1;
}

常见误区

  • 误区:next 从 -1 开始;正解:Java 常用 0 开始。
  • 误区:失配时 j = 0;正解:j = next[j-1]。

追问 / 延伸

  • Q:KMP 时间复杂度? A:O(n+m)。
  • Q:KMP 用于什么? A:单模式匹配。

02.12.4-006 字符串哈希

频率 ★★★★ | 难度 基础

一句话结论

字符串哈希把字符串映射成整数:hash(s) = s[0]*base^(n-1) + s[1]*base^(n-2) + ... + s[n-1];用前缀和 O(1) 求任意子串哈希;双哈希降低冲突。

概念解释

  • base:进制,如 131 或 13331。
  • 前缀哈希:h[i] = h[i-1]*base + s[i]。
  • 子串哈希:h[r] - h[l-1]*base^(r-l+1)。

原理流程

  1. 预处理前缀哈希和 base 的幂。
  2. 子串 [l,r] 哈希 = h[r] - h[l-1]*base^(r-l+1)。
  3. 双哈希:两个不同 base 和 mod,降低冲突。

代码 / 示例

class StrHash {
    private final long[] h, p;
    private final int base = 131;
    private final long mod = 1000000007;

    StrHash(String s) {
        int n = s.length();
        h = new long[n + 1]; p = new long[n + 1];
        p[0] = 1;
        for (int i = 0; i < n; i++) {
            h[i + 1] = (h[i] * base + s.charAt(i)) % mod;
            p[i + 1] = (p[i] * base) % mod;
        }
    }
    long query(int l, int r) { // 1-indexed
        return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
    }
}

常见误区

  • 误区:子串哈希公式写错;正解:h[r] - h[l-1]*base^(r-l+1)。
  • 误区:不用 mod;正解:不用 mod 会溢出,用 mod 或 unsigned long 自然溢出。

追问 / 延伸

  • Q:哈希冲突怎么办? A:双哈希(两个 base 和 mod)。
  • Q:字符串哈希用于什么? A:子串比较、回文判断、最长公共子串。

02.12.4-007 AC 自动机 vs Trie

频率 ★★★ | 难度 基础

一句话结论

Trie 是单模式/多模式字典树,但失配时只能从头开始;AC 自动机在 Trie 上建 fail 指针,失配时跳到最长可匹配后缀,实现多模式高效匹配。

概念解释

  • Trie:字典树,前缀匹配。
  • AC 自动机:Trie + fail 指针,多模式匹配。
  • 区别:Trie 失配从头,AC 失配跳 fail。

原理流程

  1. Trie:插入模式串,扫描文本。
  2. AC 自动机:Trie + fail 指针,扫描时失配跳 fail。

代码 / 图示

Trie:
  插入模式串
  扫描文本,失配从头

AC 自动机:
  Trie + fail 指针
  扫描文本,失配跳 fail

常见误区

  • 误区:Trie 就是 AC 自动机;正解:AC 自动机 = Trie + fail 指针。
  • 误区:Trie 能做多模式匹配;正解:Trie 可以,但效率低,AC 自动机更高效。

追问 / 延伸

  • Q:Trie 用于什么? A:前缀匹配、自动补全。
  • Q:AC 自动机用于什么? A:敏感词过滤、多模式匹配。

02.12.4-008 各算法复杂度对比

频率 ★★★ | 难度 基础

一句话结论

KMP O(n+m),AC 自动机 O(n+m+z),Manacher O(n),字符串哈希 O(n) 预处理 O(1) 查询,后缀数组 O(n log n) 预处理 O(log n) 查询。

概念解释

  • KMP:单模式匹配。
  • AC 自动机:多模式匹配。
  • Manacher:最长回文。
  • 字符串哈希:子串比较。
  • 后缀数组:后缀排序。

原理流程

见表格。

代码 / 图示

算法         预处理     查询       用途
KMP         O(m)      O(n)       单模式匹配
AC 自动机   O(m)      O(n+z)     多模式匹配
Manacher    -         O(n)       最长回文
字符串哈希   O(n)      O(1)       子串比较
后缀数组     O(n log n) O(log n)  后缀排序

常见误区

  • 误区:KMP 是 O(n);正解:KMP 是 O(n+m),m 为模式串长度。
  • 误区:Manacher 是 O(n^2);正解:Manacher 是 O(n)。

追问 / 延伸

  • Q:现场写哪个? A:KMP、字符串哈希、Manacher 现场可写;AC 自动机和后缀数组一般不要求现场写。
  • Q:怎么选? A:单模式 KMP,多模式 AC 自动机,子串比较哈希,回文 Manacher。

待整理清单

  • [ ] 后缀自动机 SAM
  • [ ] Z 算法
  • [ ] 字符串哈希双哈希实现