Ternary Strings Avoiding 012 — Solution & Editorial

Back to the Problem

Build the KMP automaton for the forbidden pattern; states are the length of the current matched prefix. The transfer matrix (rejecting transitions that complete the pattern) raised to the N-th power counts safe strings.

Complexity: O(m³ log N)

Watch out: The automaton must use the KMP failure function so overlapping partial matches transition correctly.