الگوریتم KMP،یکی از الگوریتم‌های مطرح در علوم کامپیوتر است که می‌تواند تمام رخدادهای یک رشته به طول $m$ را در یک رشته به طول $n$ پیدا کند. منظور از یک رخداد یک زیررشته‌ی متوالی است که با رشته‌ی مورد نظر برابر است.
بدیهی ترین الگوریتم برای پیدا کردن رخدادها بررسی تمام زیررشته‌های متوالی به طول $m$ به صورت جداگانه است. پیچیدگی زمانی این روش $O(nm)$ خواهد بود در حالی که الگوریتم KMP در پیچیدگی زمانی $O(n + m)$ و حافظه‌ی $O(m)$ موفق به پیدا کردن تمام رخدادها می‌شود.
فرض کنید می‌خواهیم رخدادهای $t$ در $s$ را پیدا کنیم. زیررشته‌ی متوالی حروف $i$ تا $j$ یک رشته مانند $a$ را با $a[i..j]$ نشان می‌دهیم. فرض کنید $T(i)$ بلندترین پیشوند از $t$ باشد که پسوند $t[0..i - 1]$ نیز هست اما با آن برابر نیست. برای $i = 0$، فرض می‌کنیم $T(0) = -1$ و $T(1) = 0$. برای مثال:
i 0 1 2 3 4 5 6 W[i] A B C D A B D T[i] -1 0 0 0 0 1 2
فرض کنید بتوانیم این تابع را در $O(m)$ برای $t$ محاسبه کنیم. الگوریتم KMP با استفاده از این تابع می‌تواند در $O(n + m)$ مسئله‌ی یافتن رخدادها را حل کند. برای این‌کار الگوریتم روی حروف $s$ حرکت می‌کند و با اضافه شدن هر حرف، عدد $x$ را به روزرسانی می‌کند طوری که عدد $x$ بعد از اضافه شدن حرف $i$ برابر با طول بلندترین پیشوند $t$ باشد که پسوند $s[0..i]$ است.
برای این‌کار کافی است به این نکته توجه شود که در هر لحظه $s[i - x + 1..i] = t[0..x - 1]$ و به ازای هر $y > x$ ، $s[i - y + 1..i] \ne t[0..y - 1]$. بنابراین اگر $s[i - z + 1..i + 1] = t[0..z - 1]$ داریم $z <= x + 1$. بنابراین در محاسبه‌ی $x$ پس از اضافه شدن حرف $i + 1$ ام تنها زیررشته‌ی $s[i - x + 1..i + 1]$ موثر است. براساس همین استدلال می‌توان به صورت استقرایی نتیجه گرفت که برای محاسبه‌ی $x$ بعدی می‌توان از تکه‌کد زیر استفاده کرد:
while x > -1 and t[x] != s[i + 1] # Note that x is length and t is zero-base indexed x = T(x) x = x + 1
حال اگر به ازای هر $i$، مقدار $x$ برابر $m$ ، طول رشته‌ی $t$ شود یک رخداد پیدا می‌شود.
فرض شد که بتوانیم قسمت اول الگوریتم، یعنی محاسبه‌ی $T(i)$ را در $O(m)$ انجام دهیم. جهت بررسی پیچیدگی ساده‌تر قسمت دوم فرض کنید $j = i - x + 1$ در این صورت مقدار $i + j$ اکیدا صعودی است. در ابتدا $i + j = 0$ و در انتها $i + j <= 2n$ پس در کل پیچیدگی زمانی این قسمت از الگوریتم از $O(n)$ خواهد بود. پس به طور کلی پیچیدگی زمانی الگوریتم $O(n + m)$ خواهد بود.
تابع $T(i)$ را تابع شکست (failure function) رشته‌ی $t$ می‌گویند. برای محاسبه‌ی این تابع در ابتدا می‌دانیم $T(0) = -1$ و $T(1) = 0$. حال دقیقا مطابق استدلال‌هایی که در قسمت اصلی الگوریتم انجام شد می‌توان $T(j)$ را از روی $T(j - 1)$ محاسبه کرد.
کد زیر پیاده‌سازی مشابهی از الگوریتم KMP است.
void preKmp(char *x, int m, int kmpNext[]) { int i, j; i = 0; j = kmpNext[0] = -1; while (i < m) { while (j > -1 && x[i] != x[j]) j = kmpNext[j]; i++; j++; if (x[i] == x[j]) kmpNext[i] = kmpNext[j]; else kmpNext[i] = j; } } void KMP(char *x, int m, char *y, int n) { int i, j, kmpNext[XSIZE]; /* Preprocessing */ preKmp(x, m, kmpNext); /* Searching */ i = j = 0; while (j < n) { while (i > -1 && x[i] != y[j]) i = kmpNext[i]; i++; j++; if (i >= m) { OUTPUT(j - i); i = kmpNext[i]; } } }