{"id":"kmp-lps-fallback-invariant","text":"In the KMP implementation, the LPS array satisfies `0 <= lps[i] < i+1` for all `i`, and on mismatch the fallback `length = lps[length - 1]` guarantees forward progress — every search iteration either advances the haystack pointer or decreases the pattern pointer.","truth_value":"IN","source":"entries/2026/06/06/find-the-index-of-the-first-occurrence-in-a-string-solution.md","source_url":"","source_hash":"","justifications":[],"dependents":[],"metadata":{},"created_at":"","updated_at":"","reviewed_at":"","verified_at":"","retracted_at":"","explanation":{"steps":[{"node":"kmp-lps-fallback-invariant","truth_value":"IN","reason":"premise"}]}}