Suffix Structures Checkpoint

1. Rolling hash lets you compare substrings in:

O(1) time after preprocessing O(n) time always O(log n) time O(n log n) time

2. Using two moduli reduces the chance of hash collisions.

3. A suffix array is:

The list of suffix indices in sorted order A trie of prefixes A hash map of substrings A tree of palindromes

4. Suffix automata can compute:

Number of distinct substrings Minimum spanning tree Shortest path in DAG Median of array