快捷導(dǎo)航

深入串的模式匹配算法(普通算法和KMP算法)的詳解

更新時(shí)間：2013年05月29日 09:19:02 作者：

本篇文章是對(duì)串的模式匹配算法(普通算法和KMP算法)的應(yīng)用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

串的定位操作通常稱作串的模式匹配，是各種處理系統(tǒng)中的最重要操作之一。
模式匹配最樸素的算法是回溯法，即模式串跟主串一個(gè)字符一個(gè)字符的匹配，當(dāng)模式串中跟主串不匹配時(shí)，主串回溯到與模式串匹配開始的下一個(gè)位置，模式串回溯到第一個(gè)位置，繼續(xù)匹配。算法的時(shí)間復(fù)雜度為O（m*n），算法如下：

復(fù)制代碼代碼如下:

//樸素的串的模式匹配算法，S為主串，T為模式串，即找S中有沒有與T相同的字串
int Index(char *S, char *T, int pos)//pos記錄從哪一位開始匹配可以直接用0代替
{
 int i=pos, j=0; 
 while(i <strlen(S) && j <strlen(T))//確保未超出字符串的長度
 {
  if (S[i] == T[j])
      { ++i; ++j;} //如果相同，則繼續(xù)向后比較
  else 
      {i = i-j+1; j =0;} //如果不同，就回溯，重新查找
 }
 if (j == strlen(T))
  return i-strlen(T); //若匹配成功，返回S中與T字符串相同開始位置的索引
 else return 0; //若匹配不成功，返回0
}

O（m*n）的時(shí)間復(fù)雜度有點(diǎn)大，于是人們發(fā)現(xiàn)了KMP算法，核心思想是：當(dāng)不匹配發(fā)生時(shí)，主串不回溯，模式串回溯到“合適”的位置，哪個(gè)位置合適，只與模式串有關(guān)，所以可以先算出模式串中各個(gè)字符，當(dāng)不匹配發(fā)生是，應(yīng)該回溯到哪個(gè)位置。算法整體時(shí)間復(fù)雜度O(m+m)。
算法如下：

復(fù)制代碼代碼如下:

void GetNext(char* T, int *next)
{
 int i=1,j=0; 
 next[1]=0;
 while( i < strlen(T) )
 { 
  if (j == 0 || T[i] == T[j])
  {
    ++i; ++j; 
    next[i] = j;
  } 
  else j = next[j];
 }
} 
int KMP(char* S, char* T, int pos)
{
 int i = pos, j = 1;
 while (i)
 {
  if (S[i] == T[j])
  { 
   ++ i;  ++ j;
  } 
  else 
   j = next[j]; 
 }
 if (j > strlen(T)) 
  return i-T[0];
 else 
  return 0; 
} 

求next的操作不是最優(yōu)的，因?yàn)樗麤]有考慮aaaaaaaaaaaaaaaaaaab的情況，這樣前面會(huì)出現(xiàn)大量的1，這樣的算法復(fù)雜度已經(jīng)和最初的樸素算法沒有區(qū)別了。所以稍微改動(dòng)一下：

復(fù)制代碼代碼如下:

void GetNextEx(char *T, int *next)
{
 int i=1,j=0; next[1] = 0;
 while(i < strlen(T))
 {
  if (j == 0 || T[i] == T[j])
  {
   ++i; ++j;
   if (T[i] == T[j])
    next[i] = next[j];  //減少回退次數(shù)
   else   next[i] = j;  //和上面算法一樣next[i]=j
  }
  else j = next[j]; 
 } 
} 