Algoritmalar
en

KMP

Strings O(n + m) O(m)

Knuth-Morris-Pratt: precomputes a longest-prefix-suffix table so a mismatch never rescans the text — linear-time pattern matching.

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 — a single character has no proper prefix.

Invariantlps[i] is the longest proper prefix of p[0..i] that is also its suffix. That is why i never moves backwards: on a mismatch only j slides.

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++;
        }
    }
}

How KMP works

Precompute, for each pattern prefix, the longest proper prefix that is also a suffix (LPS). On a mismatch the pattern slides to that border instead of restarting — the text pointer never backs up.

When to use it

Repeated searches with one pattern, streaming input where re-reading text is impossible.