Strings Avoiding 1010 — Solution & Editorial

Back to the Problem

KMP-automaton transfer matrix (states = matched-prefix length, rejecting completion) raised to the N-th power.

Complexity: O(m³ log N)