Properties

≤ 2N-1 states, ≤ 3N-4 transitions. Each state represents equivalence class of substrings.

Advertisement

Online construction

Extend by one character. Split states if needed. Each character: amortized O(σ) time.

Advertisement

Substring queries

Occurrence: walk transitions per pattern char. Distinct substrings: sum of (len - link.len) over states. Kth substring: dp on state.

Applications

Substring matching. Longest common substring of two strings. Multiple substring queries on same text.