字符串

本文内容参考《算法》，《算法导论》，OI Wiki。

字符串匹配

例题

• 28. 找出字符串中第一个匹配项的下标。

暴力

• 时间复杂度：最坏 \(O(NM)\)，平均 \(O(N)\)。
• 空间复杂度：\(O(1)\)。

private static int bruteForce(String text, String pattern) {
    int i, j;
    int n = text.length(), m = pattern.length();
    for (i = 0, j = 0; i < n && j < m; i++) {
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        } else {
            i -= j;
            j = 0;
        }
    }
    return j == m ? i - m : -1;
}

KMP

• 时间复杂度：\(O(N)\)。
• 空间复杂度：\(O(M)\)。

private static int kmp(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    if (m > n) return -1;
    
    // 处理模式串
    // next[i] 表示 pattern 的子串 [0, i] 的最长相等前后缀的长度
    int[] next = new int[m];
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    
    // 匹配文本串
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

Boyer-Moore

• 时间复杂度：最坏 \(O(NM)\)，平均 \(O(\frac{N}{M})\)。
• 空间复杂度：\(O®\)。

System.out.println("TODO");

Rabin-Karp

• 时间复杂度：\(O(N)\)。
• 空间复杂度：\(O(1)\)。

private static final int P = 13331;

// MOD = 2^64
private static int rabinKarp(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    if (m > n) return -1;

    long PM = pow(P, m - 1);
    long patHash = hash(pattern, m);
    long txtHash = hash(text, m);
    if (txtHash == patHash) {
        return 0;
    }

    for (int i = m; i < n; i++) {
        txtHash = txtHash - text.charAt(i - m) * PM;
        txtHash = txtHash * P + text.charAt(i);
        if (txtHash == patHash) {
            return i - m + 1;
        }
    }
    return -1;
}

private static long pow(int a, int n) {
    long res = 1L, x = a;
    for (; n != 0; x *= x, n >>= 1) {
        if ((n & 1) == 1) {
            res *= x;
        }
    }
    return res;
}

private static long hash(String s, int m) {
    long h = 0L;
    for (int i = 0; i < m; i++) {
        h = h * P + s.charAt(i);
    }
    return h;
}

字符串哈希

例题

• E. Compress Words（这题使用 \(MOD=2^{64}\) 一直在第 65 个测试点 WA，看来还是模质数比较好）。

实现

• 时间复杂度：预处理 \(O(N)\)，获取哈希值 \(O(1)\)。
• 空间复杂度：\(O(N)\)。

class StringHash {
    private final int K = 2;
    private static final long[] b = {131, 13331};
    private static final long[] m = {1_000_000_007, 998244353};

    private int index;
    private final long[][] h, p;

    public StringHash(int n) {
        h = new long[K][n + 1];
        p = new long[K][n + 1];
        for (int i = 0; i < K; i++) {
            p[i][0] = 1;
        }
    }

    public StringHash(char[] s) {
        this(s.length);
        for (char c : s) add(c);
    }

    public void add(char c) {
        for (int j = 0; j < K; j++) {
            p[j][index + 1] = p[j][index] * b[j] % m[j];
            h[j][index + 1] = (h[j][index] * b[j] + c) % m[j];
        }
        index++;
    }

    public long[] get(int l, int r) {
        long[] res = new long[K];
        for (int i = 0; i < K; i++) {
            long t = h[i][r + 1] - h[i][l] * p[i][r - l + 1];
            res[i] = (t % m[i] + m[i]) % m[i];
        }
        return res;
    }

    public int length() {
        return index;
    }
}

字典树（Trie）

例题

• 208. 实现 Trie (前缀树)。
• 1803. 统计异或值在范围内的数对有多少。

实现

• 时间复杂度：插入和查找都是 \(O(k)\)，其中 \(k\) 为字符串的长度。
• 空间复杂度：\(O(nR)\)，其中 \(n\) 为节点总数，\(R\) 为字母表大小。

class Trie {
    private static final int R = 26;
    private final Node root;

    private static class Node {
        boolean exist;
        Node[] next = new Node[R];
    }

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.next[idx] == null) {
                node.next[idx] = new Node();
            }
            node = node.next[idx];
        }
        node.exist = true;
    }

    public boolean search(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.next[idx] == null) {
                return false;
            }
            node = node.next[idx];
        }
        return node.exist;
    }
}

AC 自动机

例题

• P5357 【模板】AC 自动机（二次加强版）。

实现

• 时间复杂度：插入 \(O(k)\)，构建 \(O(nR)\)，查询 \(O(k+n)\)，其中 \(k\) 为字符串的长度。
• 空间复杂度：\(O(nR)\)，其中 \(n\) 为节点总数，\(R\) 为字母表大小。

class AhoCorasickAutomaton {
    private static final int R = 26;
    private final Node root;

    // 按插入顺序存储模式串尾字符对应的节点
    private final List<Node> patternNodes;

    // 所有节点按层次遍历顺序存储（代码没有存根节点）
    private final List<Node> levelOrderNodes;

    private static class Node {
        int cnt; // 节点出现在文本串中的次数，懒更新
        Node fail; // 节点的失配指针，指向当前节点的最长后缀节点
        Node[] next = new Node[R];
    }

    public AhoCorasickAutomaton() {
        root = new Node();
        patternNodes = new ArrayList<>();
        levelOrderNodes = new ArrayList<>();
    }

    // 插入模式串
    public void insert(String pattern) {
        Node node = root;
        for (int i = 0; i < pattern.length(); i++) {
            int idx = pattern.charAt(i) - 'a';
            if (node.next[idx] == null) {
                node.next[idx] = new Node();
            }
            node = node.next[idx];
        }
        patternNodes.add(node);
    }

    // 构建失配指针和 Trie 图
    public void build() {
        // 将根节点的直接子节点入队，并构建节点的失配指针和 Trie 图
        // 提前入队是因为根节点和其直接子节点与其他节点的处理逻辑不同
        root.fail = root;
        Queue<Node> q = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            if (root.next[i] == null) {
                root.next[i] = root;
            } else {
                root.next[i].fail = root;
                q.offer(root.next[i]);
            }
        }
        // 层次遍历，构建失配指针和 Trie 图
        while (!q.isEmpty()) {
            Node node = q.poll();
            levelOrderNodes.add(node);
            for (int i = 0; i < R; i++) {
                if (node.next[i] == null) {
                    node.next[i] = node.fail.next[i];
                } else {
                    node.next[i].fail = node.fail.next[i];
                    q.offer(node.next[i]);
                }
            }
        }
    }

    // 查询每个模式串在文本串中的出现次数
    public void query(String text, int[] cnt) {
        // 懒更新出现次数
        Node node = root;
        for (int i = 0; i < text.length(); i++) {
            int idx = text.charAt(i) - 'a';
            node = node.next[idx];
            node.cnt++;
        }
        // 倒序层次遍历，进一步沿着失配指针传递出现次数
        // 倒序遍历是因为失配指针必然在更上层，所以从下向上传递可以保证正确性
        for (int i = levelOrderNodes.size() - 1; i >= 0; i--) {
            node = levelOrderNodes.get(i);
            node.fail.cnt += node.cnt;
        }
        // 获取每个模式串的出现次数
        for (int i = 0; i < patternNodes.size(); i++) {
            cnt[i] += patternNodes.get(i).cnt;
        }
    }
}

正则表达式

例题

• 10. 正则表达式匹配。使用动态规划或者构造非确定有限状态自动机（NFA）。

实现

• 时间复杂度：构造 NFA \(O(m)\)，匹配 \(O(nm)\)，其中 \(m\) 为正则表达式的长度，\(n\) 为文本串的长度。
• 空间复杂度：构造 NFA \(O(m)\)，匹配 \(O(m)\)。

System.out.println("TODO");