Longest Repeated Substring, in depth: suffix arrays and LCP, rolling-hash binary search, non-overlapping and k-times variants, and corpus-scale dedup

The core idea: repeats are shared suffix prefixes

Every substring is a prefix of some suffix. A substring occurs twice exactly when two different suffixes share it as a prefix, so the longest repeated substring is the longest common prefix (LCP) of any two distinct suffixes. Checking all pairs costs O(n²) comparisons; sorting fixes that. In sorted order, the LCP of any two suffixes equals the minimum of the adjacent LCPs between them, so the largest pairwise LCP always appears between neighbours. The answer is the maximum of the LCP array.

The naive alternative, generating all substrings and counting them, is O(n³) time or O(n²) memory and fails beyond a few thousand characters. It remains valuable as a test oracle.

Suffix array plus LCP

The standard solution builds a suffix array, computes the LCP array with Kasai's algorithm, and takes the maximum. Construction is covered in depth in the suffix array construction article, and Kasai's linear-time LCP pass in the LCP array article; here is a compact, tested version of both.

def suffix_array(s):
    """Prefix doubling: O(n log^2 n) with Python's sort. Fine to ~10^6 chars."""
    n = len(s)
    sa, rank, k = list(range(n)), [ord(ch) for ch in s], 1
    while n > 1:
        key = lambda i: (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)
        new = [0] * n
        for j in range(1, n):
            new[sa[j]] = new[sa[j - 1]] + (key(sa[j - 1]) < key(sa[j]))
        rank = new
        if rank[sa[-1]] == n - 1:
            break
        k *= 2
    return sa


def lcp_kasai(s, sa):
    """lcp[i] = LCP(suffix sa[i-1], suffix sa[i]); lcp[0] = 0. O(n)."""
    n = len(s)
    rank = [0] * n
    for i, p in enumerate(sa):
        rank[p] = i
    lcp, h = [0] * n, 0
    for p in range(n):
        if rank[p] == 0:
            h = 0
            continue
        q = sa[rank[p] - 1]
        while p + h < n and q + h < n and s[p + h] == s[q + h]:
            h += 1
        lcp[rank[p]] = h
        if h:
            h -= 1
    return lcp


def lrs(s):
    if len(s) < 2:
        return ""
    sa = suffix_array(s)
    lcp = lcp_kasai(s, sa)
    i = max(range(1, len(s)), key=lcp.__getitem__)
    return s[sa[i]:sa[i] + lcp[i]]

Kasai's trick is that when you move from suffix p to suffix p + 1, the LCP with its sorted predecessor drops by at most one, so h never restarts from zero and the total work is linear. For banana the arrays are sa = [5, 3, 1, 0, 4, 2] and lcp = [0, 1, 3, 0, 0, 2]; the maximum, 3, sits at rank 2, suffix 1, giving ana. For production, swap the doubling sort for an SA-IS library and keep Kasai as is.

Rolling hash with binary search

If you do not have a suffix array library, a rolling hash with binary search on the length is short and fast. The key observation is monotonicity: if some substring of length L repeats, its prefix of length L minus 1 repeats too, so the set of feasible lengths is an interval starting at zero and binary search applies. Each probe hashes all windows of length L in O(n) using the polynomial hashing prefix technique.

import random

def lrs_hash(s):
    n = len(s)
    MOD = (1 << 61) - 1
    B = random.randrange(1 << 20, MOD - 1)      # random base defeats crafted collisions
    pre, pw = [0] * (n + 1), [1] * (n + 1)
    for i, ch in enumerate(s):
        pre[i + 1] = (pre[i] * B + ord(ch)) % MOD
        pw[i + 1] = pw[i] * B % MOD

    def repeat_of_length(L):
        seen = {}
        for i in range(n - L + 1):
            x = (pre[i + L] - pre[i] * pw[L]) % MOD
            j = seen.setdefault(x, i)
            if j != i and s[j:j + L] == s[i:i + L]:   # verify: never trust a hash
                return i
        return -1

    best, at, lo, hi = 0, 0, 1, n - 1
    while lo <= hi:                  # a repeat of length L implies one of L - 1
        mid = (lo + hi) // 2
        i = repeat_of_length(mid)
        if i >= 0:
            best, at, lo = mid, i, mid + 1
        else:
            hi = mid - 1
    return s[at:at + best]

On banana, the search range is 1 to 5; it probes L = 3 (found ana), then L = 4 (none: no window of four letters repeats), and stops with length 3 after two linear scans instead of five. Expected time is O(n log n) plus verification cost. The direct string comparison on a hash match keeps the answer correct; the remaining risk is a collision between two different windows causing a true repeat to be missed for that probe, which with a 61-bit modulus and random base is vanishingly rare but not impossible. If you need a guaranteed answer, use the suffix array.

The variants you actually need

Non-overlapping repeats. In banana, ana overlaps itself; the longest non-overlapping repeat is an (positions 1 and 3). Binary search on L again works: walk the suffix array in groups where adjacent LCP is at least L, track the minimum and maximum start position in each group, and accept L if max minus min is at least L. The comparison must be >= L, not > L; two copies that touch end to start do not overlap.

At least k occurrences. k suffixes share a prefix of length equal to the minimum LCP across the k minus 1 adjacent gaps between them. Slide a window of k minus 1 LCP values with a monotonic deque and take the best window minimum:

from collections import deque

def lrs_at_least_k(s, k):          # k >= 2
    n = len(s)
    if n < k:
        return ""
    sa = suffix_array(s)
    lcp = lcp_kasai(s, sa)
    w, best, at, dq = k - 1, 0, 0, deque()
    for i in range(1, n):
        while dq and lcp[dq[-1]] >= lcp[i]:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - w:
            dq.popleft()
        if i >= w and lcp[dq[0]] > best:
            best, at = lcp[dq[0]], sa[i]
    return s[at:at + best]

Across documents. To find text repeated between documents, concatenate them with separators that occur nowhere else, ideally a distinct separator per document, or by mapping to an integer alphabet with reserved values. Without them, a match can run across a document boundary. To require the two occurrences to come from different documents, which is the longest common substring problem, keep a position-to-document array and only count adjacent pairs whose documents differ.

All variants, including the non-overlapping check, were tested against a brute-force oracle on thousands of random strings over two- and three-letter alphabets, which is where off-by-one bugs live.

Choosing a method

With a suffix automaton, the answer is the longest state whose end-position set has size at least two, computed by propagating occurrence counts along suffix links. It is elegant for online input, but the suffix array is easier to debug and its memory is predictable. The suffix array deep dive compares these structures more broadly.

At corpus scale: deduplicating training data

The most visible modern use is training-data deduplication. Lee et al., in Deduplicating Training Data Makes Language Models Better (ACL 2022), concatenated a corpus into one sequence, built a suffix array over it and removed verbatim repeated spans longer than a 50-token threshold; they report a single 61-word sentence repeated over 60,000 times in C4. Their open-source tool, deduplicate-text-datasets, is a practical starting point.

• Work on tokens or bytes, deliberately. Byte-level arrays are simple and language-agnostic; token-level arrays align thresholds with what the model sees. Mixing them makes thresholds meaningless.
• Size the integers. A suffix array over more than about two billion positions needs 64-bit (or 40-bit packed) entries, and the LCP array doubles memory again. Plan for several bytes per input byte, and build out of core when it does not fit.
• Report the threshold, not the maximum. In data work you rarely want only the single longest repeat; you want every maximal repeat above a length, which is every LCP run at or above the threshold.
• Normalise first. Unicode normalisation and whitespace handling decide whether visually identical text counts as repeated.

Reporting every repeat above a threshold is one linear pass over the LCP array: a run of adjacent entries at or above L is a group of suffixes sharing at least L leading characters.

def groups_at_least(s, sa, lcp, L):
    """Yield start positions of suffixes that share at least L leading characters."""
    if not s:
        return
    group = [sa[0]]
    for i in range(1, len(s)):
        if lcp[i] >= L:
            group.append(sa[i])
        else:
            if len(group) > 1:
                yield sorted(group)
            group = [sa[i]]
    if len(group) > 1:
        yield sorted(group)

As a worked example, take three log lines joined with two different separators that occur nowhere else: user=17 login ok|user=42 login ok#user=17 logout. With L = 8 the pass yields six groups: positions [7, 24] share login ok, positions [0, 34] share user=17 log, and four more are the same two repeats shifted right by a character or two. Keep only left-maximal groups, where the characters just before the starts differ or a start is 0, and two remain. Had both separators been |, login ok|user= would have matched across line boundaries, which is the separator bug in miniature.

Failure modes

• Comparing suffixes as strings in the sort. sorted(range(n), key=lambda i: s[i:]) is O(n² log n) time and copies O(n²) characters; it passes small tests and dies on real input.
• Missing separators. Repeats spanning document boundaries are reported as real.
• Off-by-one in non-overlap. Using > L misses touching copies; forgetting the reset at a group boundary merges unrelated suffixes.
• Trusting hashes. Without the verification compare, a collision returns a substring that does not repeat at all.
• Empty and single-character inputs. max() over an empty range raises; guard lengths below 2.
• Degenerate strings. aaaa... makes naive LCP scans quadratic; Kasai stays linear, a hand-rolled pairwise loop does not.

What to do next

1. Implement the brute-force oracle first and keep it in your test suite.
2. Build SA plus Kasai, check banana gives ana and aaaa gives aaa, then run randomised comparisons.
3. Add the non-overlapping and at-least-k variants and test them against the oracle.
4. Decide byte versus token level for your data, and pick unique separators per document.
5. For corpus work, try deduplicate-text-datasets on a sample and measure memory per input byte.
6. Report every repeat above a threshold, review a sample by hand, then set the threshold.