CF 105537L - Longest Common Substring

We are given two strings, and we want to determine the length of the longest contiguous segment that appears in both strings. A contiguous segment here means a substring, so characters must match in order and without gaps.

codeforcescompetitive-programming

CF 105537L - Longest Common Substring

Rating: -
Tags: -
Solve time: 46s
Verified: yes

Solution

Problem Understanding

We are given two strings, and we want to determine the length of the longest contiguous segment that appears in both strings. A contiguous segment here means a substring, so characters must match in order and without gaps.

The input consists of two lines, each containing a string over some alphabet. The output is a single integer representing the maximum length of a substring that exists somewhere inside both strings.

The constraints are large enough that any approach that compares all substrings explicitly becomes infeasible. If both strings have length up to around 10^5, then enumerating all substrings would already imply roughly O(n^2) candidates per string, and comparing them would explode to at least O(n^3) in a naive form. Even optimized substring comparisons that rely on hashing but still iterate all pairs would be too slow in the worst case.

This immediately suggests that the solution must avoid explicit enumeration of substrings and instead rely on a structure that compresses repeated substring comparisons.

A few edge situations matter in practice. If one string is empty, the answer is zero. If the strings share no common characters, the answer is zero as well, even if both are long. If the strings are identical, the answer is the full length of the string. A more subtle case is repeated characters, for example "aaaaa" and "aaa", where the answer is the minimum length, and naive substring matching can easily overcount overlaps unless handled carefully.

Approaches

The brute-force idea is straightforward. We generate every substring of the first string and every substring of the second string, and compare them to find the longest match. Even if we try to optimize comparisons using hashing, the number of substrings is still quadratic, so we end up with roughly O(n^2) substrings per string and O(1) or O(log n) comparison per pair depending on implementation. This becomes too large quickly.

A slightly better brute approach is to fix a pair of starting positions, one in each string, and extend while characters match. For each pair, we grow a matching window. This is correct because any common substring must correspond to some aligned starting positions. However, this still examines O(n^2) pairs and can expand up to O(n) per pair in the worst case, producing O(n^3) behavior on adversarial inputs like repeated characters.

The key observation is that instead of checking every substring independently, we can treat the problem as finding the longest common prefix between all suffixes of the two strings. If we consider every suffix of the first string and every suffix of the second string, then any common substring is exactly a common prefix of some pair of suffixes. This transforms the problem into finding the maximum LCP value over all suffix pairs.

A suffix array or suffix automaton naturally captures all suffixes and their relationships. The suffix automaton approach is particularly clean here. A suffix automaton compactly represents all substrings of a string, and each state corresponds to a set of substrings with the same end positions. When we scan the second string through the automaton built from the first string, we can track the longest substring ending at each position that appears in the first string.

This reduces the problem from comparing all substring pairs to a single linear scan over the second string while maintaining a current match state in the automaton.

Approach Time Complexity Space Complexity Verdict
Brute Force O(n³) O(1) Too slow
Suffix Automaton O(n) O(n) Accepted

Algorithm Walkthrough

We build a suffix automaton for the first string, then simulate walking through the second string on this automaton while tracking the longest valid match ending at each position.

  1. Build a suffix automaton from the first string. Each state stores transitions for characters, a suffix link, and the maximum length of substrings represented by that state. This structure compresses all substrings of the first string into O(n) states.
  2. Initialize two variables, state pointing to the initial automaton state and length representing the current matched substring length.
  3. Iterate through each character of the second string from left to right.
  4. If there is a transition from the current state using the current character, follow it and increase length by one. This means we have extended a valid substring that exists in the first string.
  5. If there is no such transition, we repeatedly follow suffix links until we find a state that has a transition with the current character or we reach the root. While doing this, we also reduce length accordingly because we are shortening the matched suffix until it becomes valid again.
  6. If we find a valid transition after fallback, take it and set length to the length of that transition state plus one. If not, reset state and length to zero.
  7. Track the maximum value of length over all positions in the second string. This value is the answer.

The fallback step is necessary because the current match is only valid if it corresponds to a substring in the first string. When a mismatch occurs, we must find the longest suffix of the current substring that still appears in the automaton.

Why it works

The suffix automaton encodes every substring of the first string as a path from the root. At any point during the scan of the second string, the algorithm maintains the invariant that length corresponds to the longest suffix of the processed prefix of the second string that is also a substring of the first string, and state is the automaton state representing that substring. Any time a mismatch occurs, following suffix links effectively removes characters from the left of the current substring in decreasing order of length until a valid transition exists again. Because suffix links represent the longest proper suffix that is also a prefix in the automaton sense, this guarantees we never skip a valid candidate substring and never overestimate the match length.

Python Solution

import sys
input = sys.stdin.readline

class State:
    __slots__ = ("next", "link", "length")
    def __init__(self):
        self.next = {}
        self.link = -1
        self.length = 0

def build_sa(s):
    st = [State()]
    last = 0

    for ch in s:
        cur = len(st)
        st.append(State())
        st[cur].length = st[last].length + 1

        p = last
        while p != -1 and ch not in st[p].next:
            st[p].next[ch] = cur
            p = st[p].link

        if p == -1:
            st[cur].link = 0
        else:
            q = st[p].next[ch]
            if st[p].length + 1 == st[q].length:
                st[cur].link = q
            else:
                clone = len(st)
                st.append(State())
                st[clone].length = st[p].length + 1
                st[clone].next = st[q].next.copy()
                st[clone].link = st[q].link

                while p != -1 and st[p].next[ch] == q:
                    st[p].next[ch] = clone
                    p = st[p].link

                st[q].link = st[cur].link = clone

        last = cur

    return st

def longest_common_substring(s, t):
    sa = build_sa(s)

    v = 0
    l = 0
    best = 0

    for ch in t:
        if ch in sa[v].next:
            v = sa[v].next[ch]
            l += 1
        else:
            while v != -1 and ch not in sa[v].next:
                v = sa[v].link
            if v == -1:
                v = 0
                l = 0
                continue
            l = sa[v].length + 1
            v = sa[v].next[ch]

        if l > best:
            best = l

    return best

s = input().strip()
t = input().strip()
print(longest_common_substring(s, t))

The solution begins by constructing a suffix automaton over the first string. Each state stores transitions in a dictionary, a suffix link, and the maximum length of substrings represented by that state. The construction ensures that every substring of the first string corresponds to some path in the automaton.

During the scan of the second string, we maintain a current state and a match length. If we can extend using the current character, we do so directly. Otherwise, we walk suffix links until we either find a valid transition or return to the root. The length is adjusted to reflect the longest valid suffix that still exists in the automaton. The answer is the maximum match length encountered during this scan.

A subtle detail is the reset behavior when we fall back to the root and still cannot transition. Without explicitly resetting both state and length, stale match lengths can propagate incorrectly and overcount matches.

Worked Examples

Consider s = "ababc" and t = "babca".

We track how the scan progresses over t.

Character State transition Length Best
b root → b 1 1
a b → ba 2 2
b ba → bab 3 3
c bab → babc 4 4
a mismatch, fallback to a 1 4

This demonstrates how the automaton extends matches greedily and only falls back when necessary, preserving the longest valid substring.

Now consider s = "aaaaa" and t = "aaa".

Character State transition Length Best
a extend 1 1
a extend 2 2
a extend 3 3

This case shows repeated characters, where the automaton stays in a highly reusable region and continuously extends matches.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each character is processed once, and suffix link traversal amortizes to linear time over all transitions
Space O(n) The automaton stores a linear number of states and transitions

The construction cost is linear in the size of the first string, and the scan is linear in the size of the second string. This fits comfortably within typical constraints up to 10^5.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    s = inp.strip().split()
    if len(s) == 2:
        from sys import stdin
    import sys
    input = sys.stdin.readline

    class State:
        __slots__ = ("next", "link", "length")
        def __init__(self):
            self.next = {}
            self.link = -1
            self.length = 0

    def build_sa(s):
        st = [State()]
        last = 0
        for ch in s:
            cur = len(st)
            st.append(State())
            st[cur].length = st[last].length + 1
            p = last
            while p != -1 and ch not in st[p].next:
                st[p].next[ch] = cur
                p = st[p].link
            if p == -1:
                st[cur].link = 0
            else:
                q = st[p].next[ch]
                if st[p].length + 1 == st[q].length:
                    st[cur].link = q
                else:
                    clone = len(st)
                    st.append(State())
                    st[clone].length = st[p].length + 1
                    st[clone].next = st[q].next.copy()
                    st[clone].link = st[q].link
                    while p != -1 and st[p].next[ch] == q:
                        st[p].next[ch] = clone
                        p = st[p].link
                    st[q].link = st[cur].link = clone
            last = cur

        return st

    def solve(s, t):
        sa = build_sa(s)
        v = 0
        l = 0
        best = 0
        for ch in t:
            if ch in sa[v].next:
                v = sa[v].next[ch]
                l += 1
            else:
                while v != -1 and ch not in sa[v].next:
                    v = sa[v].link
                if v == -1:
                    v = 0
                    l = 0
                    continue
                l = sa[v].length + 1
                v = sa[v].next[ch]
            best = max(best, l)
        return str(best)

    s, t = inp.strip().split()
    return solve(s, t)

# provided samples
assert run("ababc babca") == "4", "sample 1"

# custom cases
assert run("a a") == "1", "single char match"
assert run("abc def") == "0", "no overlap"
assert run("aaaaa aaa") == "3", "repeated characters"
assert run("abcd abcd") == "4", "full match"
Test input Expected output What it validates
a a 1 minimal identical strings
abc def 0 no common substring
aaaaa aaa 3 repeated character compression
abcd abcd 4 full string match

Edge Cases

For empty or single-character strings, the automaton still behaves correctly because the root state either has no transitions or a single transition. For "a" and "a", the scan immediately follows a valid transition and produces length 1.

For repeated-character strings like "aaaaa" and "aaa", every step stays within a small cycle in the automaton. The fallback logic is never triggered, which confirms that the algorithm does not require explicit substring enumeration.

For completely disjoint alphabets, for example "abc" and "xyz", every character causes a fallback to the root state and immediate reset of the match length. The best value remains zero throughout, since no transitions ever succeed.