Reusing overlap in the matched prefix
After a partial match fails, naive search can retry characters just examined. KMP asks whether a suffix of the matched region is also a pattern prefix and therefore remains useful.
For example, aba is both a prefix and suffix of ababa. Preprocessing records such fallback possibilities so a mismatch discards only impossible progress. The reasoning uses exact character relationships rather than predicting future text.
References: [1]
Failure links and automaton states
A failure-link implementation falls back to shorter candidate prefixes and tests the current text character again. The pattern state can retreat while text positions continue forward rather than restarting text scans.
A full deterministic table instead records the next state for every state–character pair. Princeton’s KMP example uses this DFA representation. It shares the overlap idea with failure links, but table storage also depends on alphabet size.
Linear search has implementation conditions
For a nonempty pattern, failure-link variants support O(m) preprocessing and storage followed by O(n) first-occurrence search. Total fallback work is bounded through accumulated forward progress. A full R-character transition table instead needs O(Rm) preparation and storage.
Character representation still determines offset units. Reporting all matches requires retaining appropriate overlap after a hit rather than blindly skipping the whole pattern. A changed pattern also requires new preprocessing.