الگوریتم 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]≠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]; } } }