Vyhledávání KMP

O(n + m)

Naivní vyhledávání po každé neshodě začne vzor od začátku a znovu porovnává znaky, které už sedělo. KMP se tomu vyhne. Nejdřív sestaví tabulku LPS (nejdelší vlastní prefix, který je zároveň sufixem) pro každý prefix vzoru — zobrazená jako malá čísla pod vzorem. Pak prochází text dvěma ukazateli: při shodě se oba posunou; při neshodě, místo aby vrátil ukazatel v textu, posune vzor dopředu podle LPS, která říká, kolik už sedícího prefixu je stále použitelné. Protože ukazatel v textu nikdy necouvá, běží v O(n + m). LPS je ten celý trik — zakóduje sebepodobnost vzoru, takže žádné porovnání nepřijde nazmar. Nalezené shody se zvýrazní zeleně.

Text a vzor
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Předpočítej tabulku LPS — pro každý prefix vzoru jeho nejdelší prefix, který je zároveň sufixem.
  2. Procházej text a vzor společně; při shodě posuň oba.
  3. Při neshodě posuň vzor dopředu podle LPS (nevracej se v textu).
  4. Když sedí celý vzor, zaznamenej výskyt a posuň se dál hledat další.

Pseudokód

1kmp(text, pattern):                 # O(n + m)2  build lps[]: lps[i] = length of the longest3    proper prefix of pattern[0..i] that is also a suffix4  i ← 0 (text), j ← 0 (pattern)5  while i < n:6    if text[i] = pattern[j]: i++, j++; if j = m: report match, j ← lps[j-1]7    else if j > 0: j ← lps[j-1]      # slide, keep matched prefix8    else: i++