====== الگوریتم 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$.  برای مثال:

<code>
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
</code>

فرض کنید بتوانیم این تابع را در $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$ بعدی می‌توان از تکه‌کد زیر استفاده کرد:
<code>
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
</code>

حال اگر به ازای هر $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 است.

<code c>
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];
      }
   }
}
</code>
===== مراجع =====

  * [[http://www-igm.univ-mlv.fr/~lecroq/string/node8.html]]
  * [[https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm]]