Suffix Structures & Rolling Hash

  • Rolling hash = O(1) substring compare
  • Suffix array = sorted suffixes + LCP
  • Suffix automaton = compact substring DFA
1 / 4

Rolling hash

  • pref[i+1] = pref[i]*B + s[i]
  • hash(l..r) in O(1)
  • Double hash to reduce collisions
2 / 4

Suffix array

  • Sort suffix indices
  • LCP for repeated substrings
3 / 4

Suffix automaton

  • O(n) build
  • Count distinct substrings
4 / 4
Use arrow keys or click edges to navigate. Press H to toggle help, F for fullscreen.