====== الگوریتم KMP ======
===== تعریف =====
الگوریتم 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];
}
}
}
===== مراجع =====
* [[http://www-igm.univ-mlv.fr/~lecroq/string/node8.html]]
* [[https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm]]