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

المپدیا

فهرست مندرجات

الگوریتم KMP

تعریف