Referanseside · Kapittel 31

Begreper & formler

Alle nøkkelbegrepene og formlene fra Strengmatching, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards7 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Naiv algoritme

Sjekker mønsteret i alle posisjoner; $O ((n - m + 1) m)$ tid.

02Knuth–Morris–Pratt (KMP)

Bruker prefiksfunksjon for å unngå sammenligninger som allerede er gjort.

03Rabin–Karp

Bruker hashing for raskt å sammenligne mønstre; $O (n + m)$ forventet tid.

04Prefiksfunksjon

For hvert indeks $q$ i $P$ angir lengden på lengste prefiks som også er suffiks.

05Z-algoritme

Alternativ lineær algoritme for mønstergjenkjenning basert på Z-verdier.

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

O (n + m)

H (s) = (s_{0} p^{m - 1} + s_{1} p^{m - 2} + \dots + s_{m - 1}) mod M