题目简述：

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

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

题目链接：1044. 最长重复子串

字符串哈希 + 二分查找

这是我最推荐的方案，性能很好的同时代码也不会弯弯绕绕。本文的其他算法已经在事实上远不是开发岗位需要掌握的程度了，理论和代码上复杂度都很高。

思路

考虑 Rabin–Karp 算法编码，对每个固定长度 $L$ 的子数组计算多项式哈希，定义索引范围 $[i,i+L)$ 上的哈希函数为 $$ H_{i,L}=(s_iB^{L-1}+s_{i+1}B^{L-2}+\cdots+s_{i+L-1}B^0)\mod{M} $$ 其中 $B$ 为所选取的基数，$M$ 为足够大的质数，例如经典的 1_000_000_007L 与 1_000_000_009L，应满足 $1<B<M$。通常 $B$ 会选择一个较大的随机数。

如果希望降低哈希碰撞的概率，可用考虑双模哈希校验，选择两对 $(B_1,M_1)$ 与 $(B_2,M_2)$，考虑两个哈希函数同时校验。

对于一个确定的 $L$，这将产生 $n-L+1$ 个哈希值。比较哈希值以快速判断是否存在重复子数组。

为了以 $O(1)$ 的时间代价实现哈希查询，构造前缀哈希数组，定义前缀索引范围 $[0,i]$ 上的哈希值为 $$ H[i]=(s_0B^i+s_1B^{i-1}+\cdots+s_iB^0)\mod{M} $$ 同时，预定义 $powB[k]=B^k\mod{M}$ 数组。那么，对于义索引范围 $[i,i+L)$ 上的哈希函数，其值为 $$ H_{i,L}=(H[i+L-1]-H[i-1]\cdot B^{L})\mod{M} $$ 事实上，应使用 1-based 编码以考虑 $s$ 的索引 $-1$ 前缀哈希。

如果存在一个长度为 $L$ 的重复子数组，那么必然存在 $\forall L'<L$ 长度的重复子数组；如果不存在一个长度为 $L$ 的重复子数组，那么 $\forall L'>L$ 长度的重复子数组均不存在。此处存在单调性，因此可以利用二分查找算法迅速找到分界点。

代码

算法的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

可以看到，针对本问题字符串哈希 + 二分查找的表现已经十分亮眼了。后文的方案性能上均十分强劲，但都没有本方案简单好写。

算法中因为利用了哈希判等，因此不属于完全确定性的算法——至少，是否产生哈希碰撞与 $B,M$ 的选择以及输入字符串有关。

class Solution {

    private static final Random rand = new Random("Hoshino Ichika".hashCode());
    public static final long M1 = 1_000_000_007L;
    public static final long M2 = 1_000_000_009L;
    public static final long B1 = rand.nextLong(2, M1);
    public static final long B2 = rand.nextLong(2, M2);
    public long[] POW_B1;
    public long[] POW_B2;

    public String longestDupSubstring(String s) {
        int n = s.length();
        POW_B1 = new long[n + 1];
        POW_B2 = new long[n + 1];
        POW_B1[0] = 1;
        POW_B2[0] = 1;
        for (int i = 1; i <= n; i++) {
            POW_B1[i] = mod((POW_B1[i - 1] * B1), M1);
            POW_B2[i] = mod((POW_B2[i - 1] * B2), M2);
        }

        long[] preHash_1 = buildPrefixHash(s, M1, B1);
        long[] preHash_2 = buildPrefixHash(s, M2, B2);

        /* 二分搜索子串长度 L */
        int lo = 1;
        int hi = s.length() - 1;
        int loc = -1;
        while (lo <= hi) {
            int L = lo + (hi - lo) / 2;

            int tmp = findDupSubstring(s, preHash_1, preHash_2, L);
            if (tmp == -1) {
                hi = L - 1;
            } else {
                lo = L + 1;
                loc = tmp;
            }
        }

        if (loc == -1) return "";
        return s.substring(loc, loc + hi);
    }

    /* 1-based */
    public long[] buildPrefixHash(String s, long M, long B) {
        long[] prefixHash = new long[s.length() + 1];

        for (int i = 1; i <= s.length(); i++) {
            prefixHash[i] = mod(prefixHash[i - 1] * B + s.charAt(i - 1), M);
        }

        return prefixHash;
    }

    /* 利用前缀哈希数组，查询 [i, i + L) 上子串的哈希值 */
    public long hash(long[] prefixHash, long M, long[] powB, int i, int L) {
        return mod(prefixHash[i + L] - prefixHash[i] * powB[L], M);
    }

    /* 返回重复子串的起始索引，如果不存在重复子串则约定返回 -1 */
    public int findDupSubstring(String s, long[] preHash_1, long[] preHash_2, int L) {
        Set<Long> hashes = new HashSet<>((int) ((s.length() - L + 1) / 0.75f) + 1);

        for (int i = 0; i <= s.length() - L; i++) {
            long h1 = hash(preHash_1, M1, POW_B1, i, L);
            long h2 = hash(preHash_2, M2, POW_B2, i, L);
            long key = (h1 << 32) | (h2 & 0xffffffffL);
            if (hashes.contains(key)) return i;
            hashes.add(key);
        }

        return -1;
    }

    private long mod(long x, long m) {
        return (x % m + m) % m;
    }
}

SA + 基数排序 + Kasai LCP

补充阅读：二分搜索 + 哈希(Rabin-Karp) ❌ 后缀数组 ✔

思路

首先得到所有后缀，记后缀数组为 SA，对 SA 按字典序排序。

定义 LCP 数组为排序后 SA 中相邻后缀的最长公共前缀长度，例如 lcp[i] 表示排序后 sa[i] 与 sa[i+1] 的最长公共前缀长度，最后 LCP 中的最大值即为最长字符串的长度，对应的 SA 中的元素即为最长重复子串。

仔细想想，为什么这样能够保证得到最长重复子串呢？设某个重复子串在 s 中出现了至少两次，那么它必然分别是至少两个后缀的公共前缀。将所有后缀按字典序排序后，拥有该公共前缀的一段后缀会在后缀数组中形成一个连续区间，而这段区间内必然存在某对相邻后缀，它们的 LCP 至少等于这个重复子串的长度。因此，只需要考察排序后相邻后缀的最长公共前缀长度，取其中最大值，就能得到全局最长重复子串。

朴素的做法是真的存储所有后缀再排序，接着再对每两个相邻的排序后后缀双指针寻找最长公共前缀的长度，但这样做的话时间复杂度为 $O(n^2)$，空间复杂度也为 $O(n^2)$，在力扣的测试数据范围下必然超时。

要避免超时，务必解决下面三个关键问题：

对于 SA，我们不必真的存储所有的后缀，存储所有后缀的索引即可，于是空间开销降至 $O(n)$；
对 SA 排序时不要像这样重写比较器：
```
Integer[] sa = new Integer[n];
for (int i = n - 1; i >= 0; i--) sa[i] = i;
Arrays.sort(sa, (a, b) -> {
    while (a < n && b < n) {
        if (s.charAt(a) > s.charAt(b)) {
            return 1;
        } else if (s.charAt(a) < s.charAt(b)) {
            return -1;
        } else {
            a++;
            b++;
        }
    }
    return a == n ? -1 : 1;
});
```
这必然导致排序需要付出 $O(n^2\log n)$ 的时间开销代价，必然超时。

应考虑基数排序，比较容易实现的方案是考虑倍增法，步骤为：
1. 初始化秩数组 rank、计数桶尺寸 size 与计数桶数组 cnt，rank 可以用后缀首字符值或递增序列初始化，size 初始化为 rank 值域宽度加一；
2. 在倍增主循环 k = 1, 2, 4, ... 中维护每轮循环的二元键序，定义 key[i] = (rank[i], rank[i+k])，如果 i + k 索引越界则视 rank[i+k] = -1，含义为小于任何合法秩；
3. 对二元键序中的第二个值进行排序，
  - 首先遍历所有二元键序的第二个值，用计数桶 cnt 统计值出现的频数；
  - 计算 cnt 的前缀和数组，可以就地直接修改 cnt，即 cnt[q] += cnt[q-1]；
  - 根据 cnt 倒着放置元素，索引 i 从 n - 1 遍历至 0，令 idx = sa[i]，取第二关键字 sec = (idx + k < n) ? (rank[idx + k] + 1) : 0，执行 tmpSA[--cnt[sec]] = idx；该过程为稳定放置（后出现者先占位）。
4. 对二元键序中的第一个值进行排序（同样使用稳定计数排序），
  - 将计数桶清零，遍历 tmpSA，统计第一关键字频数：fir = rank[idx] + 1，做 cnt[fir]++；
  - 对 cnt 做前缀和；
  - 倒序稳定放置回 sa：从 i = n - 1 至 0，idx = tmpSA[i]，fir = rank[idx] + 1，执行 sa[--cnt[fir]] = idx。
5. 依据新顺序重标秩，
  - 设 tmpRank[sa[0]] = 0，classes = 1；
  - 对 i = 1..n-1：令 a = sa[i-1]，b = sa[i]，若 (rank[a] != rank[b]) || ( (a + k < n ? rank[a + k] : -1) != (b + k < n ? rank[b + k] : -1) )，则 classes++；随后令 tmpRank[b] = classes - 1；
  - 交换引用：rank ←→ tmpRank。
6. 维护桶尺寸并判断是否提前结束，
  - 若 classes == n，说明所有后缀秩已互异，排序完成，跳出主循环；
  - 否则更新计数桶尺寸 size = classes + 1，并将 cnt[0..size-1] 清零，为下一轮计数排序做准备。
7. 将窗口翻倍，令 k <<= 1，回到步骤 3–6 继续下一轮；
8. 主循环结束后，sa 即为目标后缀数组；如需 LCP，可在 O(n) 时间内用 Kasai 算法计算：构造 pos[sa[i]] = i，用复用指针 h 作为下界，依次填充 lcp[pos[i]]，每轮结束若 h > 0 则令 h--。
对于 LCP，可以用严格 $O(n)$ 时间开销的 Kasai 算法代替最坏 $O(n^2)$ 时间复杂度的朴素双指针：
1. 按原字符串的索引进行遍历，假设对原字符串中以 s[i] 开头的后缀排序后在 SA 中的顺序是 k，初始化已知公共前缀长度 m = 0；
2. 如果 k 是最大的字典序，即不存在右邻居，则重设 m = 0，并且跳过本轮循环；
3. 否则，取右邻居后缀的起点 j = sa[k + 1]，现在可以肯定这两个相邻字典序的后缀数组已经拥有长为 m 的公共前缀，于是从两个后缀的第 m + 1 位开始比较 s[i+m] 与 s[j+m]，如果匹配则 m++ 并继续比较，直到指针越界或不再匹配；
4. 更新 lcp[k] = m，如果 m > 0 则令 m--（意味着去掉首字符后公共前缀至多减少 1），然后为下一轮计算提供已知公共前缀长度的下界。

可以看到，本方案异常繁琐，仅是以上三点就非常复杂了。因此我最推荐字符串哈希 + 二分查找的方案，性能优秀的同时代码也不难编写。

代码

我们所实现的算法时间复杂度为 $O(n\log n)$、空间复杂度为 $O(n)$，是完全确定性的算法，但常数相比字符串哈希大的多。

但即便是 $O(n\log n)$ 的理论时间复杂度，实际时间开销也相当惊人了：

如果将排序算法改为 DC3 等算法，则时间复杂度能够像 SAM 一样达到线性复杂度 $O(n)$，想必结果会更加惊艳吧。

class Solution {
    public String longestDupSubstring(String s) {
        int n = s.length();

        int[] sa = new int[n];
        sortSA(s, sa);

        int[] mapCharToLexiOrder = new int[n];  // 将 s[i] 映射至对应后缀的字典序
        for (int i = 0; i < n; i++) {
            mapCharToLexiOrder[sa[i]] = i;
        }
    
        int[] lcp = new int[n];
        String res = kasai(s, lcp, sa, mapCharToLexiOrder);
        return res;
    }

    /* 倍增法基数排序，可以用朴素双指针重写 Integer[] 的比较器，但这样最坏时间复杂度将达到 O(n²log n) */
    /* 可以替换为更高级的 DC3 等算法，能够做到线性时间复杂度 O(n) */
    public void sortSA(String s, int[] sa) {
        int n = s.length();
        if (n == 0) return;
        for (int i = 0; i < n; i++) sa[i] = i;

        int[] rank = new int[n];
        int maxChar = 0;
        for (int i = 0; i < n; i++) {
            rank[i] = s.charAt(i);
            if (rank[i] > maxChar) maxChar = rank[i];
        }
        int[] tmpSA = new int[n];
        int[] tmpRank = new int[n];

        final int MAX = Math.max(n, maxChar + 1) + 2;
        int[] cnt = new int[MAX];

        int classes = maxChar + 1;
        for (int k = 1; k < n; k <<= 1) {
            int K = classes + 1;

            Arrays.fill(cnt, 0, K, 0);
            for (int i = 0; i < n; i++) {
                int idx = sa[i];
                int sec = (idx + k < n) ? (rank[idx + k] + 1) : 0;
                cnt[sec]++;
            }
            for (int i = 1; i < K; i++) cnt[i] += cnt[i - 1];
            for (int i = n - 1; i >= 0; i--) {
                int idx = sa[i];
                int sec = (idx + k < n) ? (rank[idx + k] + 1) : 0;
                tmpSA[--cnt[sec]] = idx;
            }

            java.util.Arrays.fill(cnt, 0, K, 0);
            for (int i = 0; i < n; i++) cnt[rank[i] + 1]++;
            for (int i = 1; i < K; i++) cnt[i] += cnt[i - 1];
            for (int i = n - 1; i >= 0; i--) {
                int idx = tmpSA[i];
                sa[--cnt[rank[idx] + 1]] = idx;
            }

            tmpRank[sa[0]] = 0;
            int newClasses = 1;
            for (int i = 1; i < n; i++) {
                int a = sa[i - 1], b = sa[i];
                int ra1 = rank[a], rb1 = rank[b];
                int ra2 = (a + k < n) ? rank[a + k] : -1;
                int rb2 = (b + k < n) ? rank[b + k] : -1;
                if (ra1 != rb1 || ra2 != rb2) newClasses++;
                tmpRank[b] = newClasses - 1;
            }

            int[] t = rank; rank = tmpRank; tmpRank = t;
            classes = newClasses;
            if (classes == n) break;
        }
    }

    /* 也可以替换为逻辑更简单的朴素双指针，但这样最坏时间复杂度将达到 O(n²) */
    public String kasai(String s, int[] lcp, int[] sa, int[] mapCharToLexiOrder) {
        int n = s.length();
        int m = 0;  // 已知公共前缀长度
        int longestLen = 0;
        int longestStart = -1;

        for (int i = 0; i < n; i++) {
            int k = mapCharToLexiOrder[i];
            if (k == n - 1) {
                m = 0;
                continue;
            }
            int j = sa[k + 1];
            while (i + m < n && j + m < n) {
                if (s.charAt(i + m) == s.charAt(j + m)) m++;
                else break;
            }
            lcp[k] = m;
            if (m > longestLen) {
                longestLen = m;
                longestStart = i;
            }
            if (m > 0) m--;
        }

        if (longestLen == 0) return "";
        return s.substring(longestStart, longestStart + longestLen);
    }
}

后缀自动机 SAM

理论参考

主要理论参考：后缀自动机 (SAM)

一些观点补充：后缀自动机学习笔记

在 SAM 的 DAG 模型中出现过两次以上的子串即为重复子串，取其中最长的即为问题的解。

代码

class SAM {
    
    static final int ALPHA = 26;

    int[][] next;    // 转移
    int[] link;      // 后缀链接
    int[] len;       // 到该状态的最长串长度
    int[] firstpos;  // 该状态覆盖的最长串的一个右端点位置
    long[] occ;      // endpos 集合大小（出现次数）
    int last;        // 表示整个串的“末尾状态”
    int sz;          // 状态数

    public SAM(int n) {
        int cap = 2 * n + 5;
        next = new int[cap][ALPHA];
        for (int i = 0; i < cap; i++) Arrays.fill(next[i], -1);
        link = new int[cap];
        Arrays.fill(link, -1);
        len = new int[cap];
        firstpos = new int[cap];
        Arrays.fill(firstpos, -1);
        occ = new long[cap];

        sz = 1;  // 初始化状态 0
        last = 0;
    }

    public void extend(int c, int pos) {
        int cur = sz++;
        len[cur] = len[last] + 1;
        firstpos[cur] = pos;
        occ[cur] = 1;  // 新增结尾
        int p = last;

        while (p != -1 && next[p][c] == -1) {
            next[p][c] = cur;
            p = link[p];
        }
        if (p == -1) {
            link[cur] = 0;
        } else {
            int q = next[p][c];
            if (len[p] + 1 == len[q]) {
                link[cur] = q;
            } else {
                int clone = sz++;
                // 克隆 q
                System.arraycopy(next[q], 0, next[clone], 0, ALPHA);
                len[clone] = len[p] + 1;
                link[clone] = link[q];
                firstpos[clone] = firstpos[q];
                occ[clone] = 0;  // 克隆不新增结尾

                while (p != -1 && next[p][c] == q) {
                    next[p][c] = clone;
                    p = link[p];
                }
                link[q] = link[cur] = clone;
            }
        }
        last = cur;
    }

    // 计数排序：按 len 从小到大顺序
    public int[] orderByLen() {
        int maxLen = 0;
        for (int i = 0; i < sz; i++) maxLen = Math.max(maxLen, len[i]);
        int[] cnt = new int[maxLen + 1];
        for (int i = 0; i < sz; i++) cnt[len[i]]++;
        for (int i = 1; i <= maxLen; i++) cnt[i] += cnt[i - 1];
        int[] ord = new int[sz];
        for (int i = sz - 1; i >= 0; i--) ord[--cnt[len[i]]] = i;
        return ord;
    }

    // occ 沿 suffix link 从子到父汇总
    public void accumulateOcc() {
        int[] ord = orderByLen();
        for (int i = sz - 1; i >= 0; i--) {
            int v = ord[i];
            if (link[v] != -1) occ[link[v]] += occ[v];
        }
    }
}

class Solution {
    public String longestDupSubstring(String s) {
        int n = s.length();
        if (n <= 1) return "";
        SAM sam = new SAM(n);
        for (int i = 0; i < n; i++) {
            sam.extend(s.charAt(i) - 'a', i);
        }
        sam.accumulateOcc();

        int bestLen = 0;
        int bestPos = -1;

        for (int v = 0; v < sam.sz; v++) {
            if (sam.occ[v] >= 2 && sam.len[v] > bestLen) {
                bestLen = sam.len[v];
                bestPos = sam.firstpos[v];
            }
        }
        if (bestLen == 0) return "";
        return s.substring(bestPos - bestLen + 1, bestPos + 1);
    }
}

Ukkonen 后缀树

难度太大，这里就不考虑了。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

字符串哈希 + 二分查找

思路

代码

SA + 基数排序 + Kasai LCP

思路

代码

后缀自动机 SAM

理论参考

代码

Ukkonen 后缀树

FilesExpand file tree

1044. 最长重复子串：LRS，考虑 Rabin–Karp 字符串哈希 + 二分查找，或者其他基于后缀的方案（SA + 基数排序 + Kasai LCP、后缀自动机 SAM、Ukkonen 后缀树）.md

Latest commit

History

1044. 最长重复子串：LRS，考虑 Rabin–Karp 字符串哈希 + 二分查找，或者其他基于后缀的方案（SA + 基数排序 + Kasai LCP、后缀自动机 SAM、Ukkonen 后缀树）.md

File metadata and controls

字符串哈希 + 二分查找

思路

代码

SA + 基数排序 + Kasai LCP

思路

代码

后缀自动机 SAM

理论参考

代码

Ukkonen 后缀树