【综合笔试题】两种强有力的字符串处理方式

宫水三叶的刷题日记

发布于 2022-05-25 08:12:10

4290

发布于 2022-05-25 08:12:10

文章被收录于专栏：宫水三叶的刷题日记

题目描述

这是 LeetCode 上的「1044. 最长重复子串」，难度为「困难」。

Tag : 「字符串哈希」、「二分」、「后缀数组」

给你一个字符串 s ，考虑其所有重复子串：即 s 的连续子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回任意一个可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

示例 1：

输入：s = "banana"

输出："ana"

示例 2：

输入：s = "abcd"

输出：""

提示：

2 <= s.length <= 3 * 10^4
s 由小写英文字母组成

字符串哈希 + 二分

题目要求得「能取得最大长度的任一方案」，首先以「最大长度」为分割点的数轴具有「二段性」：

小于等于最大长度方案均存在（考虑在最大长度方案上做删减）；
大于最大长度的方案不存在。

二分范围为 [0, n] ，关键在于如何 check 函数，即实现「检查某个长度 len 作为最大长度，是否存在合法方案」。

对于常规做法而言，可枚举每个位置作为起点，得到长度为 len 的子串，同时使用 Set<String> 容器记录已被处理过子串有哪些，当容器中出现过当前子串，说明存在合法方案。

但是该做法实现的 check 并非线性，子串的生成和存入容器的时执行的哈希函数执行均和子串长度相关，复杂度是 O(n * len) 。

我们可以通过「字符串哈希」进行优化，对「字符串哈希」不熟悉的同学可以看前置 🧀 字符串哈希入门。

具体的，在二分前先通过 O(n) 的复杂度预处理出哈希数组，从而确保能够在 check 时能够O(1) 得到某个子串的哈希值，最终将 check 的复杂度降为 O(n) 。

代码：

class Solution {
    long[] h, p;
    public String longestDupSubstring(String s) {
        int P = 1313131, n = s.length();
        h = new long[n + 10]; p = new long[n + 10];
        p[0] = 1;
        for (int i = 0; i < n; i++) {
            p[i + 1] = p[i] * P;
            h[i + 1] = h[i] * P + s.charAt(i);
        }
        String ans = "";
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            String t = check(s, mid);
            if (t.length() != 0) l = mid;
            else r = mid - 1;
            ans = t.length() > ans.length() ? t : ans;
        }
        return ans;
    }
    String check(String s, int len) {
        int n = s.length();
        Set<Long> set = new HashSet<>();
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            long cur = h[j] - h[i - 1] * p[j - i + 1];
            if (set.contains(cur)) return s.substring(i - 1, j);
            set.add(cur);
        }
        return "";
    }
}

时间复杂度：令 n 为字符串 s 的长度，预处理出哈希数组的复杂度为 O(n) ；二分最大长度的复杂度为 O(n\log{n}) ；整体复杂度为O(n\log{n}) 空间复杂度：O(n)

后缀数组

另外一个较为进阶的做法是使用「后缀数组」，后缀数组有基于基数排序的倍增实现，复杂度为 O(n\log{n}) ，也有基于 DC3 的 O(n) 做法。DC3 的做法已经写不出来了，写一个基于「基数排序」的倍增做法。

后缀数组包含几个核心数组：

sa 数组：字典序排名为 i 的后缀是第几个；
rk 数组：第 i 个后缀的排名是多少（不难发现 rk 与 sa 满足 sa[rk[i]] = rk[sa[i]] = i ）；
height 数组：存储 sa[i] 与 sa[i - 1] 的 LCP（最长公共前缀） 为何值。

代码：

class Solution {
    int N = 30010;
    int[] x = new int[N], y = new int[N], c = new int[N];
    int[] sa = new int[N], rk = new int[N], height = new int[N];
    void swap(int[] a, int[] b) {
        int n = a.length;
        int[] c = a.clone();
        for (int i = 0; i < n; i++) a[i] = b[i];
        for (int i = 0; i < n; i++) b[i] = c[i];
    }
    public String longestDupSubstring(String s) {
        int n = s.length(), m = 128;
        s = " " + s;
        char[] cs = s.toCharArray();
        // sa：两遍基数排序，板子背不下来也可以直接使用 sort，复杂度退化到 n \log^2 n
        for (int i = 1; i <= n; i++) {
            x[i] = cs[i]; c[x[i]]++;
        }
        for (int i = 2; i <= m; i++) c[i] += c[i - 1];
        for (int i = n; i > 0; i--) sa[c[x[i]]--] = i;
        for (int k = 1; k <= n; k <<= 1) {
            int cur = 0;
            for (int i = n - k + 1; i <= n; i++) y[++cur] = i;
            for (int i = 1; i <= n; i ++) {
                if (sa[i] > k) y[++cur] = sa[i] - k;
            }
            for (int i = 1; i <= m; i++) c[i] = 0;
            for (int i = 1; i <= n; i++) c[x[i]]++;
            for (int i = 2; i <= m; i++) c[i] += c[i - 1];
            for (int i = n; i > 0; i--) {
                sa[c[x[y[i]]]--] = y[i];
                y[i] = 0;
            }
            swap(x, y);
            x[sa[1]] = cur = 1;
            for (int i = 2; i <= n; i++) {
                if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = cur;
                else x[sa[i]] = ++cur;
            }
            if (cur == n) break;
            m = cur;
        }
        // height
        int k = 0;
        for (int i = 1; i <= n; i ++) rk[sa[i]] = i;
        for (int i = 1; i <= n; i++) {
            if (rk[i] == 1) continue;
            int j = sa[rk[i] - 1];
            k = k > 0 ? k - 1 : k;
            while (i + k <= n && j + k <= n && cs[i + k] == cs[j + k]) k++;
            height[rk[i]] = k;
        }
        int idx = -1, max = 0;
        for (int i = 1; i <= n; i++) {
            if (height[i] > max) {
                max = height[i];
                idx = sa[i];
            }
        }
        return max == 0 ? "" : s.substring(idx, idx + max);
    }
}