Longest Common Substring, in depth: the DP recurrence, suffix automaton, suffix array with LCP and binary search with rolling hashes

The problem, precisely

Let s have length n and t have length m. A substring is a contiguous slice, so s[i:i+L] for some start i and length L. We want the largest L such that some slice of s of length L equals some slice of t, plus one witness position. Ties are common; if you need all witnesses rather than any, decide that before choosing an algorithm.

Two facts carry most of the algorithms. First, every common substring is a common suffix of some prefix of s and some prefix of t, which gives the dynamic program. Second, if a common substring of length L exists then one of every shorter length exists too (take a prefix of it), so the predicate "a common substring of length L exists" is monotone in L and can be binary searched. Keep a brute-force version that tries every slice of s against t: it is the reference you test against.

The dynamic program and a worked example

Define D[i][j] as the length of the longest common suffix of s[:i] and t[:j]. If the last characters differ, no common suffix exists and the value is zero. If they match, the common suffix extends the one ending one character earlier in both strings:

D[i][j] = D[i-1][j-1] + 1   if s[i-1] == t[j-1]
D[i][j] = 0                 otherwise
answer  = max over all i, j of D[i][j]

The difference from the subsequence recurrence is the zero. In the subsequence problem a mismatch inherits the better neighbour; here a mismatch breaks the run, so the table is mostly zeros with short diagonals of increasing numbers. The worked example uses s = ABABC and t = BABCA.

Reading the table: cell (5, 4) holds 4, which means the common suffix of s[:5] = ABABC and t[:4] = BABC has length 4. The substring is therefore the last four characters of s[:5], which is BABC. The other diagonal, 1 then 2 at cells (1, 2) and (2, 3), is the shorter common substring AB.

Each cell depends only on its upper-left neighbour, so you only need the previous row. Keeping the row on the shorter string gives O(nm) time and O(min(n, m)) memory, and recording where the maximum ended gives the witness without a traceback:

def lcs_dp(s, t):
    """Longest common substring by DP with one rolling row."""
    if len(s) < len(t):
        s, t = t, s                      # keep the row on the shorter string
    prev = [0] * (len(t) + 1)
    best_len, best_end = 0, 0            # best_end: end index (exclusive) in s
    for i in range(1, len(s) + 1):
        cur = [0] * (len(t) + 1)
        si = s[i - 1]
        for j in range(1, len(t) + 1):
            if si == t[j - 1]:
                cur[j] = prev[j - 1] + 1
                if cur[j] > best_len:
                    best_len, best_end = cur[j], i
        prev = cur
    return s[best_end - best_len:best_end]

This is the right choice up to a few thousand characters per string. The ceiling is the product: two 100,000-character strings mean ten billion cell updates, roughly a quarter of an hour of this loop in CPython on a typical laptop (it measured about 2 seconds for two 5,000-character strings).

Linear time with a suffix automaton

A suffix automaton of s is the smallest deterministic automaton accepting the suffixes of s; every path from its start spells a substring of s. It has at most 2n - 1 states, is built online in amortised linear time, and each state stores its longest length, a suffix link and its transitions.

def build_sam(s):
    length, link, nxt = [0], [-1], [{}]
    last = 0
    for ch in s:
        cur = len(length)
        length.append(length[last] + 1); link.append(-1); nxt.append({})
        p = last
        while p != -1 and ch not in nxt[p]:
            nxt[p][ch] = cur
            p = link[p]
        if p == -1:
            link[cur] = 0
        else:
            q = nxt[p][ch]
            if length[p] + 1 == length[q]:
                link[cur] = q
            else:                            # split q by cloning it
                clone = len(length)
                length.append(length[p] + 1); link.append(link[q]); nxt.append(dict(nxt[q]))
                while p != -1 and nxt[p].get(ch) == q:
                    nxt[p][ch] = clone
                    p = link[p]
                link[q] = link[cur] = clone
        last = cur
    return length, link, nxt

Now stream t through the automaton of s, tracking the state and the length of the match ending at the current position. With a transition, follow it and grow the match. Without one, follow suffix links, which drop characters from the front, and reset the length to the state you fell back to; forgetting that reset is the classic bug.

def lcs_sam(s, t):
    length, link, nxt = build_sam(s)
    v, l = 0, 0                          # current state, matched length
    best_len, best_end = 0, 0            # best_end: end index (exclusive) in t
    for i, ch in enumerate(t):
        while v != 0 and ch not in nxt[v]:
            v = link[v]
            l = length[v]                # the reset people forget
        if ch in nxt[v]:
            v = nxt[v][ch]
            l += 1
        if l > best_len:
            best_len, best_end = l, i + 1
    return t[best_end - best_len:best_end]

Trace it on the example. Streaming BABCA through the automaton of ABABC, the match grows B, BA, BAB, BABC with lengths 1 to 4. The final A has no transition from the state for BABC because BABC ends s, so the walk falls back to the start state, takes A, and the length drops to 1. The best seen is 4, ending at index 4 of t: BABC again.

Reach for the automaton when one string is fixed and many are compared against it: build once, and each query costs time linear in its own length. The price is memory; a Python dictionary per state costs hundreds of bytes, so a few million characters is the practical limit.

Suffix array and LCP over a concatenation

Concatenate s + # + t + $ with separators that occur in neither string, sort all suffixes, and compute the LCP array: the longest common prefix of each adjacent pair in sorted order. The longest common substring is the largest LCP between adjacent suffixes that start on different sides of the #.

For ABABC#BABCA$, the suffix BABC#BABCA$ (from s) sits directly before BABCA$ (from t) with LCP 4. The # stops the comparison there; if it also occurred in t, a match could run across it. Construction is covered in Suffix Array Construction, in depth; the scan is short. Mapping characters to integers keeps the separators below every real symbol:

def lcs_sa(s, t):
    a = [ord(ch) + 2 for ch in s] + [1] + [ord(ch) + 2 for ch in t] + [0]
    n1 = len(s)                          # position of the separator
    sa = suffix_array(a)                 # any correct construction
    lcp = lcp_kasai(a, sa)               # lcp[i] = LCP(sa[i-1], sa[i])
    best_len, best_pos = 0, 0
    for i in range(1, len(a)):
        x, y = sa[i - 1], sa[i]
        if (x < n1) != (y < n1) and lcp[i] > best_len:
            best_len = lcp[i]
            best_pos = x if x < n1 else y    # report the slice from s
    return s[best_pos:best_pos + best_len]

With SA-IS and Kasai's LCP algorithm the pipeline is linear and the arrays are compact. The real advantage is generality. For k strings, concatenate all of them with k distinct separators, then slide a window over the sorted suffixes that covers at least one suffix from each string; the minimum LCP inside the window, maintained with a monotonic deque, is a common substring of all k. The same scan answers "all common substrings of length at least L", which is what deduplication actually needs.

Binary search with rolling hashes

Monotonicity gives a fourth method. Binary search on L; for each candidate, hash every length-L window of s into a dictionary and look up each window of t. Rolling hashes make a probe linear, so the search is O((n + m) log min(n, m)). Hash background and collision bounds are in Rabin-Karp, in depth.

M1, M2, B = (1 << 61) - 1, 1_000_000_007, 911382323

def prefix_hashes(s, mod):
    h, pw = [0] * (len(s) + 1), [1] * (len(s) + 1)
    for i, ch in enumerate(s):
        h[i + 1] = (h[i] * B + ord(ch)) % mod
        pw[i + 1] = pw[i] * B % mod
    return h, pw

def window_key(tables, i, L):                       # hash pair of x[i:i+L]
    return tuple((h[i + L] - h[i] * pw[L]) % m for (h, pw), m in zip(tables, (M1, M2)))

def window_hashes(s, L, tables):
    out = {}
    for i in range(len(s) - L + 1):
        out.setdefault(window_key(tables, i, L), i)
    return out

def lcs_hash(s, t):
    ts = [prefix_hashes(s, m) for m in (M1, M2)]     # two moduli
    tt = [prefix_hashes(t, m) for m in (M1, M2)]
    lo, hi, best = 0, min(len(s), len(t)), (0, 0)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        seen = window_hashes(s, mid, ts)             # hash pair -> start in s
        hit = None
        for j in range(len(t) - mid + 1):
            key = window_key(tt, j, mid)
            i = seen.get(key)
            if i is not None and s[i:i + mid] == t[j:j + mid]:
                hit = i                              # verified, not just hashed
                break
        if hit is not None:
            lo, best = mid, (hit, mid)
        else:
            hi = mid - 1
    return s[best[0]:best[0] + best[1]]

The verification line matters. Two moduli make a false match very unlikely for honest inputs, but adversarial inputs can collide with a known fixed base, and a false positive is silent: the search moves up and the answer is too long. Comparing slices costs O(L) and only runs on hits, so keep it.

Choosing a method

Measure on your own data before deciding: small alphabets with long repeats (DNA, logs) behave differently from prose, and Python constants can reorder the methods at moderate sizes.

At corpus scale

At corpus scale the question becomes "every long repeated span across millions of documents". Build one suffix array over the corpus; every run of adjacent suffixes with LCP at least L is a repeated span. Lee and colleagues (2021) used this on token IDs to remove repeated spans of 50 or more tokens from language-model training data. At that scale construction must be external-memory or distributed, and document boundaries need separators too, or you will report spans that straddle two documents.

Failure modes and how to test

The most useful test is a property check over two- or three-letter alphabets, where long matches actually occur: the result must occur in both inputs and match the brute-force length.

What to do next

1. Write the rolling-row DP, a brute-force reference and the small-alphabet property test first.
2. Add the verified hash method and confirm it agrees with the DP on 10,000 random pairs.
3. If one string is reused across queries, benchmark the suffix automaton at your real sizes.
4. For k strings or deduplication, build a suffix array (see Suffix Arrays, in depth) and add the windowed scan.
5. Document your unit (bytes, code points or tokens) and separator scheme in the docstring.
6. Compare this recurrence with its neighbours in Dynamic programming, in depth.