Algoritmalar
tr

KMP

Dizeler O(n + m) O(m)

Knuth-Morris-Pratt: bir uyumsuzluk metni asla yeniden taramasın diye en-uzun-önek-sonek tablosunu önceden hesaplar — doğrusal zamanda desen eşleme.

pattern
A00
B·1
A·2
B·3
C·4
A·5
B·6
A·7
B·8
i=0len=0
1/67

lps[0] = 0 — tek karakterin öz öneki yoktur.

Değişmezlps[i], p[0..i]'nin hem öz öneki hem soneki olan en uzun parçanın uzunluğudur. i'nin hiç geri gitmemesinin nedeni bu: uyuşmazlıkta yalnızca j kayar.

kmp.c
void computeLPS(const char *p, int m, int lps[]) {
    int len = 0;
    lps[0] = 0;
    for (int i = 1; i < m; ) {
        if (p[i] == p[len]) {
            lps[i++] = ++len;
        } else if (len > 0) {
            len = lps[len - 1];
        } else {
            lps[i++] = 0;
        }
    }
}
 
void kmp(const char *t, const char *p) {
    int n = strlen(t), m = strlen(p);
    int lps[m];
    computeLPS(p, m, lps);
 
    int i = 0, j = 0;
    while (i < n) {
        if (t[i] == p[j]) {
            i++; j++;
            if (j == m) {
                printf("found at %d\n", i - j);
                j = lps[j - 1];
            }
        } else if (j > 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
}

KMP nasıl çalışır?

Her desen öneki için hem önek hem sonek olan en uzun öz-öneki (LPS) önceden hesapla. Uyumsuzlukta desen baştan başlamak yerine o sınıra kayar — metin işaretçisi asla geri gitmez.

Ne zaman kullanılır?

Tek desenle tekrarlı aramalar, metnin yeniden okunamadığı akış girdileri.