Coding Interview: How Do You Search a Pattern with a Suffix Array?

Prompt and when it applies

A suffix array stores the starting index of every suffix, sorted lexicographically. When one fixed text receives many pattern queries, this index finds matches without rescanning from the beginning. Stanford CS166 asks candidates to implement searchFor, return every match, and account for the output size; here m is pattern length, n is text length, and z is the number of results.

What the interviewer is testing

• Explaining that a pattern occurrence is a suffix whose prefix equals the pattern.
• Finding the left and right boundaries with lower bounds instead of stopping at one match.
• Separating one-time construction cost from per-query cost and charging O(z) for output.
• Handling empty patterns, sentinels, duplicate suffixes, and character-comparison cost.

Clarifications to ask first

• Is the text fixed and queried many times? If it changes often, rebuilding a suffix array may not fit.
• Should the answer return all starts, only the count, or just existence?
• Are case, Unicode normalization, and byte-level ordering defined? The comparator must match the contract.
• Is the suffix array supplied, or must it be built? If building is required, is a teaching sort acceptable or is linear-time construction expected?

A 30-second answer

“Suffixes are sorted, so all suffixes beginning with pattern form one contiguous interval. I compare the pattern with text[sa[i]:] by prefix, use one binary search for the first suffix not smaller than the pattern and another for the first suffix strictly beyond that prefix. Every sa value in the interval is a match, so reporting costs O(z) and the query is O(m log n + z). By convention, an empty pattern returns n+1 positions.”

Step-by-step solution

Step 1: Define the suffix-array meaning

For banana, the suffix starts in lexicographic order are [5, 3, 1, 0, 4, 2]. The array stores integer starts, not copies of suffix strings. MIT notes describe exactly this lexicographic index and binary-search use.

Step 2: Turn matching into an interval

All suffixes beginning with ana are adjacent, so the answer is a half-open interval [left, right). The comparator needs three outcomes: the suffix prefix is below, equal to, or above the pattern. Equality must still search left and right to capture every occurrence.

Step 3: Implement two lower bounds

The first lower bound asks for the first suffix prefix that is not below the pattern. The second asks for the first suffix prefix strictly above it, or finds the right end of the equal range. Comparing the pattern with a complete suffix is wrong: a shorter suffix that is a prefix of the pattern must compare as smaller.

Step 4: Complexity and construction choices

With a supplied suffix array, each comparison examines at most m characters and binary search performs O(log n) comparisons, so the query is O(m log n + z). Stanford explicitly separates the O(z) reporting cost. A teaching build can sort suffix slices, but it copies data and is slow; production should use prefix doubling, SA-IS, or a vetted library. MIT and Stanford materials position suffix arrays as fixed-text indexes that save pointer-heavy space compared with suffix trees.

Executable Python implementation

def build_suffix_array(text):
    # Teaching build for verification, not a production complexity claim.
    return sorted(range(len(text)), key=lambda start: text[start:])


def compare_suffix_prefix(text, start, pattern):
    suffix = text[start:]
    prefix = suffix[:len(pattern)]
    if prefix < pattern:
        return -1
    if prefix > pattern:
        return 1
    if len(suffix) < len(pattern):
        return -1
    return 0


def search_with_suffix_array(text, suffix_array, pattern):
    if pattern == "":
        return list(range(len(text) + 1))

    def lower_bound(strict):
        lo, hi = 0, len(suffix_array)
        while lo < hi:
            mid = (lo + hi) // 2
            cmp = compare_suffix_prefix(text, suffix_array[mid], pattern)
            take_right = cmp < 0 or (strict and cmp == 0)
            if take_right:
                lo = mid + 1
            else:
                hi = mid
        return lo

    left = lower_bound(strict=False)
    right = lower_bound(strict=True)
    return sorted(suffix_array[left:right])

The code separates construction and querying. The final sort returns starts in text order; omit it if suffix-array order is the API contract. Empty text, empty pattern, no match, and repeated matches are direct test cases.

A high-quality sample answer

“I first confirm that the text is fixed and receives many patterns, then store every suffix start in lexicographic order. Since one pattern is a common prefix of matching suffixes, all answers occupy a contiguous range. Two lower bounds find that range; comparisons inspect only the pattern length and treat a shorter suffix as smaller. Given the array, the query is O(m log n + z), where z is output. An educational build can use sorting, but a large index needs prefix doubling, SA-IS, or a vetted implementation, with a defined character-normalization policy.”

Common mistakes

• Returning the first match → adjacent occurrences are missed → binary-search both boundaries.
• Comparing complete suffix strings with the pattern → short-suffix boundaries are wrong → define prefix comparison and the shorter-suffix rule.
• Charging construction to every query → the fixed-text scenario is not explained → report one-time build and per-query costs separately.
• Calling a suffix-array interval text order → caller sees unstable ordering → sort starts when required or document the order.
• Forgetting the n+1 empty-pattern positions → the stated contract is violated → handle the empty pattern first.

Follow-ups and strong responses

How do you reduce repeated character comparisons for a long pattern?

Add LCP information for neighboring suffixes and reuse known common prefixes during binary search. This can approach O(m + log n), but it needs extra LCP state and stronger invariants; without it, state O(m log n) honestly.

Would you use a suffix array if the text changes often?

Not as one static index. Batch rebuilds, segment-level indexes with later merges, or an online matcher may fit better. Choose based on update rate, query volume, and acceptable rebuild delay.

How do you test that binary-search boundaries are correct?

Compare against brute-force scans on random small texts and patterns. Include empty patterns, repeated characters, patterns longer than the text, no matches, and every position matching. Assert that neighboring positions outside the range fail the prefix predicate.

Why not use KMP directly?

For one pattern and one pass over the text, KMP is simpler at O(n+m). A suffix array pays off for many patterns on fixed text and for offline operations involving repeated substrings, LCP, or BWT.