Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:الگوریتم kmp

الگوریتم 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..i1] نیز هست اما با آن برابر نیست. برای 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[ix+1..i]=t[0..x1] و به ازای هر y>x ، s[iy+1..i]t[0..y1]. بنابراین اگر s[iz+1..i+1]=t[0..z1] داریم z<=x+1. بنابراین در محاسبه‌ی x پس از اضافه شدن حرف i+1 ام تنها زیررشته‌ی s[ix+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=ix+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(j1) محاسبه کرد.

پیاده‌سازی

کد زیر پیاده‌سازی مشابهی از الگوریتم 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];
      }
   }
}

مراجع


ابزار صفحه