تعاریف و مفروضات:
فرض می کنیم یه رشته داریم مثل S و می خوایم ببینیم چند بار رشته ای مثل T تکرار شده.
به رشته اصلی اصطلاحا text و به رشته ای دنبالش می گردیم، pattern می گیم.
طول text رو n فرض می کنیم و طول pattern رو m.
مثلا تو رشته aaaa رشته aa 3 بار تکرار شده.
i امین prefix رشته ای مثل S رو [S[0..i تعریف می کنیم.
i امین suffix رشته ای مثل S رو [S[i..n-1 تعریف می کنیم.
بدیهی ترین راه حل اینه که بیایم از هر نقطه شروع چک کنیم که آیا زیر رشته فعلی دقیقا برابر با pattern هست یا نه.
یعنی کاری شبیه این می کنیم:
int counter = 0;
for( int i = 0 ; i + pattern.size() <= text.size() ; i ++ )
{
bool mismatch = false;
for( int j = 0 ; j < pattern.size() ; j ++ )
if( text[i+j] != pattern[j] )
{
mismatch = true;
break;
}
if( mismatch == false )
counter ++;
}
اگه دقت کنید این پیاده سازی (O(n*m زمان نیاز داره.
سه دانشمند به نام های Knuth, Morris, Pratt الگوریتمی ابداع کردند که تو زمان (O(n+m این کار رو انجام میده. الگوریتمی که طراحی کردند به اسم سازندگانش معروف شده.( KMP )
نحوه کار الگوریتم به این شکله:
فرض کنید تو پیاده سازی بالا برای اندیسی مثل i ما تونسته باشیم k تا کاراکتر اول pattern رو match کرده باشیم و تو اندیس k+1 از pattern به mismatch رسیده باشیم.
الگوریتم بالا میاد تمام k تا match ای که داشت رو پاک می کنه و دوباره از اول برای اندیس i+1 از text کار رو تکرار می کنه.
چیزی که تو KMP اتفاق میوفته اینه که الگوریتم بر اساس یه پیش پردازشی که انجام داده، میاد یه تعداد از k تا match ای که داشت رو پاک می کنه و ادامه میده.
چطور؟
کافیه برای هر اندیس از pattern ، "طول بلندترین suffix رو بدست میارم که prefix هم باشه".
یعنی می خوایم تو i امین prefix از pattern، عددی مثل k رو پیدا کنیم که
pattern[0..k-1] == pattern[ i-k+1..i]
به عبارت دیگه، k کاراکتر اول از pattern دقیقا برابر k کاراکتر آخر از i امین prefix از pattern باشه.
مثلا برای رشته ای مثل abaab داریم:
برای اندیس 0:
0 امین prefix میشه : a
این رشته هیچ prefix ای نداره پس مقدار k0 = -1 فرض می کنیم.(قرارداد می کنیم که -1 یعنی هیچ)
برای اندیس 1:
1 امین prefix میشه : ab
این رشته یه prefix داره و یه suffix. اینجا هم باز چون برابر هم نیستند k1 = -1 میشه.
برای اندیس 2:
2 امین prefix میشه : aba
این رشته یه prefix به طول 1 داره که دقیقا برابر suffix به طول 1 ـه. پس k2 = 1 میشه.
برای اندیس 3:
3 امین prefix میشه : abaa
این رشته هم مثل حالت قبلی میشه. پس k3 = 1 میشه.
برای اندیس 4:
4 امین prefix میشه : abaab
این رشته یه prefix به طول 2 داره که برابر suffix به طول 2 ـه. پس k4 = 2 میشه.
این اطلاعات به چه درد می خوره؟
زمانی که تو اندیسی مثلا 3 از pattern یه mismatch رخ میده، می تونیم به جای اینکه کل match هایی که داشتیم رو پاک کنیم، می تونیم، 3 - K3 از match هارو پاک کنیم، ادامه بدیم.
برای اینکه واضح تر بشه روی یه مثال میگم
text = ababaabd
pattern = abaab
الگوریتم این طور کار می کنه:
3 کاراکتر اول از pattern رو match می کنه و به 4 امین کاراکتر می رسه.
چون [pattern[3] != text[3 پس یه mismatch اتفاق افتاده.
الگوریتم اول میاد تمام 3 تا match ای که داشت رو می ریزه دور و شروع می کنه از دومین کاراکتر text ادامه دادن.
اما KMP میاد میگه چون K3 = 1 بوده، پس می تونیم 1 دونه از match هایی که داشتیم رو نگه داریم و دنبال 2 امین match بگردیم.
اتفاقی که میوفته عملا اینجوریه:
شروع می کنیم به match کردن از اندیس 0 ام.
ababaabd
abaab
^
تو این اندیس mismatch داریم، الگوریتم میگه به جای اینکه برگردیم به این حالت:
ababaabd
abaab
^
از مقداری که پیش محاسبه کردیم استفاده کنیم و بریم به این حالت:
ababaabd
abaab
^
و ادامه بدیم به match کردن. چون match شده میریم جلو تا رشته رو پیدا کنیم یا دوباره mismatch ببینیم.
هر جا mismatch دیدیم، از مقادیری که محاسبه کردیم استفاده می کنیم.
چجوری این مقادیر رو حساب کنیم؟
خود نویسندگان یه الگوریتم برای پیدا کردن Ki ها ارائه دادن که اینجوریه:
int *fail[m+1];
int j = fail[0] = -1;
for( int i = 1 ; i <= m ; i ++ )
{
while( j >= 0 && pattern[j] != pattern[i-1] )
j = fail[j];
fail[i] = ++ j;
}
int count = 0, k = 0;
for( int i = 0 ; i < n ; i ++ )
{
while( k >= 0 && pattern[k] != text[i] )
k = next[k];
if( ++ k >= m )
{
k = next[k];
count ++;//match at t[i-m+1 .. i]
}
}
