Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Suffix arrays: indexed substring search and adjacent LCP

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A suffix array stores the start offsets of every suffix of an immutable text in lexicographic order. This implementation ranks one-character prefixes, then repeatedly sorts suffixes by the ranks of two adjacent blocks; doubling the block width distinguishes longer prefixes until every suffix has a unique rank. A separate linear pass records the longest common prefix of each suffix and its immediate predecessor in sorted order. Two binary searches bound the run of suffixes whose first characters equal a nonempty query pattern. The returned offsets retain suffix order, which differs from left-to-right text order.

Operational case

The incident text is valve alert valve. The pattern valve occurs at offsets 12 and 0, and the suffix array returns 12 first because the short suffix valve sorts before the longer suffix starting at 0. Alert occurs at offset 6. The suffix at 0 and the preceding suffix share the five-character prefix valve, so its adjacent LCP value is 5. The index does not record document boundaries or support inserts into the middle of the text; a changed message requires a new build.

Working Python program

python
"""Prefix-doubling suffix array, linear LCP pass, and substring lookup."""


class IncidentTextIndex:
    def __init__(self, incident_text):
        self.text = incident_text
        length = len(incident_text)
        self.suffixes = list(range(length))
        if not length:
            self.lcp = []
            return

        ranks = [ord(character) for character in incident_text]
        width = 1
        while True:
            self.suffixes.sort(key=lambda start: (ranks[start], ranks[start + width] if start + width < length else -1))
            next_ranks = [0] * length
            for offset in range(1, length):
                previous = self.suffixes[offset - 1]
                current = self.suffixes[offset]
                previous_pair = (ranks[previous], ranks[previous + width] if previous + width < length else -1)
                current_pair = (ranks[current], ranks[current + width] if current + width < length else -1)
                next_ranks[current] = next_ranks[previous] + (previous_pair != current_pair)
            ranks = next_ranks
            if ranks[self.suffixes[-1]] == length - 1:
                break
            width *= 2

        order = [0] * length
        for rank, start in enumerate(self.suffixes):
            order[start] = rank
        self.lcp = [0] * length
        matched = 0
        for start in range(length):
            rank = order[start]
            if rank == 0:
                continue
            predecessor = self.suffixes[rank - 1]
            while start + matched < length and predecessor + matched < length and incident_text[start + matched] == incident_text[predecessor + matched]:
                matched += 1
            self.lcp[rank] = matched
            if matched:
                matched -= 1

    def occurrences(self, pattern):
        if not pattern:
            raise ValueError("empty pattern has no indexed search contract")
        size = len(self.suffixes)

        def boundary(upper):
            low, high = 0, size
            while low < high:
                middle = (low + high) // 2
                prefix = self.text[self.suffixes[middle]:self.suffixes[middle] + len(pattern)]
                if prefix < pattern or (upper and prefix == pattern):
                    low = middle + 1
                else:
                    high = middle
            return low

        return self.suffixes[boundary(False):boundary(True)]


index = IncidentTextIndex("valve alert valve")
print(index.occurrences("valve"))
print(index.occurrences("alert"))
print(index.lcp[index.suffixes.index(0)])

Output

Output
[12, 0]
[6]
5

Time, space, and tradeoff

For text length N, each prefix-doubling round sorts N integer rank pairs in O(N log N) time, and there are O(log N) rounds, giving O(N log² N) construction time here and O(N) index arrays beyond the original text. The LCP pass is O(N) time and O(N) space. A pattern of length P takes O(P log N) time for two binary searches because each comparison slices up to P characters; returning Z matches adds O(Z) output space. The code does not use LCP to accelerate search. An empty pattern is rejected because reporting all N+1 insertion positions would be a different API contract.

Common Mistakes

  • Do not confuse suffix-array order with document offset order.
  • Do not quote a linear build time for this rank-doubling and sorting implementation.
  • Do not claim that computing LCP automatically accelerates the shown binary search.
  • Do not reuse the index after changing the underlying text.

Connected lessons

Apply this structure in the incident search project, then test the index decisions quiz.

Suffix automata: index substrings as text arrives adds a related operation contract.

Trigram indexes: filter and verify substring candidates adds a related indexing contract.

Palindromic trees: index distinct palindromes as text arrives adds a distinct structure contract to compare.

FM-index backward search: narrow a suffix interval by character adds a distinct structure contract to compare.

Compressed suffix trees: locate patterns across a frozen text adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details