Skip to content
Tutorials Center
My learning

Topics

Lesson 45 of 63 ยท Strings and Games

Z, Suffix Array and Aho-Corasick in Contests

Contest templates in Python: suffix array by doubling, Kasai LCP, distinct substrings, longest common substring and an Aho-Corasick automaton for many patterns.

String algorithms for contests covered hashing, the Z-function, the prefix function and Manacher's algorithm. They answer questions about one pattern against one text. This lesson adds the two heavy tools that handle everything else: the suffix array with its LCP array, which answers questions about all substrings of a string, and the Aho-Corasick automaton, which matches many patterns at once.

Both come as short templates, and each application is checked against a brute force. The theory is in Suffix Structures, Pattern Matching and Tries.

Which tool answers which question

Question Tool
Where does pattern P occur in text T? Z-function on P + "#" + T, or prefix function
Are two substrings equal? (many queries) polynomial hashing
Longest palindromic substring Manacher
Number of distinct substrings; longest repeated substring suffix array + LCP
Longest common substring of two strings suffix array of the joined string
Occurrences of many patterns in one text Aho-Corasick
K-th smallest substring, sorting all suffixes suffix array

The suffix array

The suffix array sa lists the starting positions of all suffixes of s in sorted order. For banana: the suffixes are banana, anana, nana, ana, na, a, and sorted they are a, ana, anana, banana, na, nana, so sa = [5, 3, 1, 0, 4, 2].

Sorting suffixes by comparing strings costs O(n^2 log n). The prefix-doubling method sorts by the first 2^k characters in round k: after sorting by the first k characters, each suffix has a rank; sort by the pair (rank[i], rank[i + k]) to get the order by 2k characters. After log n rounds all suffixes are distinguished. With Python's sort, that is O(n log^2 n), fine for n up to about 10^5 in a contest-sized Python run.

The LCP array lcp[i] is the length of the longest common prefix of the suffixes sa[i-1] and sa[i]. Kasai's algorithm builds it in O(n) by walking suffixes in text order and reusing the fact that when moving from suffix i to i + 1 the LCP drops by at most 1.

Python Suffix array by doubling and Kasai LCP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Three classic applications

Distinct substrings. Every substring is a prefix of some suffix. Walking suffixes in sorted order, suffix sa[i] contributes n - sa[i] prefixes, but lcp[i] of them were already counted by the previous suffix. So

TEXT
distinct substrings = n*(n+1)/2 - sum of lcp

Longest repeated substring. It is the largest value in the LCP array: two different suffixes sharing a prefix of that length.

Longest common substring of a and b. Build the suffix array of a + SEP + b where SEP is a character that occurs in neither. Then the answer is the largest lcp[i] among adjacent suffixes where one starts in a and the other in b.

Python Distinct substrings, longest repeat and longest common substring

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Aho-Corasick: many patterns at once

To find all occurrences of m patterns in a text of length n, running KMP for each pattern costs O(m * n). Aho-Corasick builds a trie of the patterns, adds failure links (like KMP's prefix function, but on the trie), and then reads the text once, so the total is O(sum of pattern lengths + n + number of matches).

  • Trie: node = a prefix of some pattern.
  • Fail link of node v (representing string w): the node for the longest proper suffix of w that is also a prefix of some pattern.
  • Automaton: precompute for every node and letter the next node, following fail links when the trie edge is missing, so reading a character is O(1).
flowchart LR
  R["root"] -->|a| A["a"]
  A -->|b| AB["ab"]
  AB -->|c| ABC["abc (pattern)"]
  R -->|b| B["b"]
  B -->|c| BC["bc (pattern)"]
  ABC -.fail.-> BC
  AB -.fail.-> B

Dashed arrows are failure links: after matching "abc", the longest suffix that is still a pattern prefix is "bc".

To count occurrences of each pattern: while scanning the text, count how many times each automaton node is visited. A visit to node v also means every node on its fail chain was matched. So after the scan, process nodes in reverse BFS order and add each node's count to the count of its fail link. The count at a pattern's end node is the number of occurrences of that pattern.

Python Aho-Corasick: occurrences of every pattern

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Duplicated patterns share the same end node and therefore get the same count, which is correct. The scan itself is one table lookup per character, so a text of 10^6 characters takes well under a second in compiled languages and a few seconds in Python.

Variations to remember

  • Does any pattern occur? Mark pattern-end nodes and propagate the mark along fail links; the text matches if it ever reaches a marked node.
  • Which patterns occur in the text? Mark visited nodes, then propagate along fail links as above and read each pattern's end node.
  • Count strings avoiding forbidden words (DP over automaton states): dp[length][node], skipping nodes that are forbidden (marked along fail links).
  • Alphabet: a list of |alphabet| ints per node keeps transitions O(1); with a large alphabet use dictionaries and fail-link walking instead.

Common mistakes

  • Using ord ranks that exceed the alphabet mapping in Aho-Corasick; map letters to 0..k-1 first.
  • Forgetting the separator in two-string suffix arrays (matches then cross the boundary). It must be a character that appears in neither string.
  • Using <= instead of < when comparing lcp values across the two strings (it picks wrong starting positions but not wrong lengths, so check what you return).
  • Calling the doubling loop with n = 0 or n = 1; handle both.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many distinct substrings does a string of length n have, given its LCP array?

    All n(n+1)/2 prefixes of suffixes are counted, but each LCP value counts prefixes already seen in the previous sorted suffix.
  2. 2. How do you find the longest common substring of strings a and b with a suffix array?

    Adjacent suffixes with a long common prefix from different strings share a substring that appears in both. The separator keeps matches from crossing the boundary.
  3. 3. What does the failure link of a node in the Aho-Corasick trie point to?

    Like the prefix function in KMP, it lets the automaton continue matching after a mismatch without restarting.
  4. 4. What is the time complexity of Aho-Corasick for m patterns of total length L and a text of length n (counting matches separately)?

    Building costs about L times the alphabet size, and scanning costs one transition per text character, independent of the number of patterns.

Summary

  • Pick the tool by question: Z or prefix function for one pattern, hashing for substring equality, suffix array plus LCP for all-substring questions, Aho-Corasick for many patterns.
  • Suffix array by prefix doubling takes O(n log^2 n) in Python; Kasai builds the LCP array in O(n).
  • Distinct substrings equal n(n+1)/2 minus the sum of the LCP values; the longest repeat is the maximum LCP; two strings need a unique separator.
  • Aho-Corasick turns a set of patterns into an automaton with failure links, scanning the text once and counting each pattern by propagating visits along fail links.
  • Test every template against brute force on tiny random strings.

Next: Project: A Local Contest Judge