KMP模式匹配算法-串的應(yīng)用

樸素匹配算法

int index（string s, string t,int pos) {  int i = pos;  / pos是指開(kāi)始搜索的位置，即開(kāi)始搜索時(shí)的下標(biāo)  int j = 0；/ 這是當(dāng)前子串的下標(biāo)  while(i < s.length() && t < b.length()) / 只有當(dāng)i小于等于主串長(zhǎng)度且j小于等于子串長(zhǎng)度時(shí)進(jìn)行循環(huán)   {    if（s[i] == t[j])     {      ++i;      ++t;    } else     {      i = i - j + 2 / i退回到上次匹配位置的下一位      j = 1;    }    if(j = b.length())    return i - b.length(); else    return 0;  }

KMP模式匹配算法

這里我們需要先明確一個(gè)概念，前綴和后綴。對(duì)于子串a(chǎn)cesdz來(lái)說(shuō)，當(dāng)j=5時(shí)，他的去掉第五個(gè)字符的子串是“aces”，前綴就是去掉再最后一個(gè)字符“s”，依次的子串，即a,ac,ace，那么后綴也很清楚了，去掉最前面一個(gè)，即s,es,ces.

? 那么next數(shù)組是怎么推導(dǎo)的呢？對(duì)于子串a(chǎn)cesdz

1）當(dāng)j=1時(shí)，next[1]=0.

2）當(dāng)j=2時(shí)，j由1到j(luò)-1就只有字符“a”,屬于其他情況next[2]=1.

3）當(dāng)j=3時(shí)，j由1到j(luò)-1的串就是“ac”，顯然“a”和”c”不等，屬于其他情況，next[3]=1.

4）以此類(lèi)推，最終next[j]為011111.

對(duì)于子串a(chǎn)ecaex

1）當(dāng)j=1時(shí)，next[1]=0.

2）當(dāng)j=2時(shí)，next[2]=1.

3）當(dāng)j=3時(shí)，next[3]=1.

4）當(dāng)j=4時(shí)，next[4]=1.

5）當(dāng)j=5時(shí)，next[5]=2.

6）當(dāng)j=6時(shí)，next[6]=3.

? ? ?我們根據(jù)經(jīng)驗(yàn)就可以知道，如果前后綴一個(gè)字符相等，那么next[j]=1+1，n個(gè)字符相等就是next[j]=1+n.

? ? ?下面我們給出next數(shù)值推導(dǎo)的代碼，

void get_next(string t, int* next) {  int i = 1;  int j = 0;  next[1] = 0;  while(i < t[0])   /*在這個(gè)位置t[0]表示t的長(zhǎng)度*/   {    if(j == 0 || t[i] == t[j])     {      ++i;      ++j;      next[i] = j;    }     else      j = next[j];  }}

? ? 下面給出具體的匹配過(guò)程的代碼

/*此處s為主串，t為子串，pos為剛開(kāi)始匹配的位置*/int kmp(string s, string t, int pos) {  int i = pos;  int j = 1;  int next[255];  get_next(t, next);  while(i <= s[0] && j <= t[0])   {    if(j == 0 || s[i] == t[j])     {      ++i;      ++j;    } else     {      j = next[j];    }  }  if(j > t[0])    return i - t[0];   else    return 0;}

? ? ?KMP算法的時(shí)間復(fù)雜度是O(n+m），相比較樸素匹配算法來(lái)說(shuō)是快了很多，但是這種優(yōu)勢(shì)只體現(xiàn)在重復(fù)部分很多的情況，否則差異不明顯。下面讓我們來(lái)看看KMP算法的進(jìn)一步優(yōu)化。

KMP的改良

?如果主串為s=aaaacde,子串為t=aaaaaz，next[j]=012345，i=5,j=5時(shí)，發(fā)現(xiàn)不匹配，此時(shí)j變?yōu)?，仍然不匹配，然后變成3，依然不匹配，后面肯定也是一樣的不匹配，因?yàn)槎际莂，那么其實(shí)這些匹配都是不必要的，可以省去。那么我們完全可以用第一位的a的next數(shù)值來(lái)代替后面a的next數(shù)值，因此我們對(duì)next進(jìn)行了改良。

void get_naxtval(string t, int* nextval) {  int i = 1;  int j = 0;  nextval[1] = 0;  while (i < t[0])   {    if (j == 0 || t[i] == t[j])     {      ++i;      ++j;      if (t[i] != t[j])      nextval[i] = j; else      nextval[i] = nextval[j];    }  }}

? 匹配算法和之前的是一樣的這里就不再重復(fù)。這里nextval的推導(dǎo)就也不重復(fù)了，和next的推導(dǎo)過(guò)程大致相同。

KMP的再改良

? ? 雖然介紹完了KMP算法的標(biāo)準(zhǔn)形式，但是，我發(fā)現(xiàn)在實(shí)際的操作中，有一些方面并不是很好操作，比如t[0],s[0]為字符串的長(zhǎng)度，這里就需要進(jìn)行一些別的操作實(shí)現(xiàn)，s[0],t[0]為字符串長(zhǎng)度，麻煩了。在最后給出我在后面改進(jìn)的KMP改良算法。希望大家在前面的內(nèi)容看明白以后，來(lái)看看這個(gè)改良版本的算法。

#include#includeusing namespace std;void get_nextval(string t, int* nextval) {  int i = 1;  int j = 0;  int l = t.length();  nextval[0] = -1;  nextval[1] = 0;  while (i   {    if (j==-1||t[i] == t[j])     {      ++i;      ++j;      if (t[i] != t[j])      nextval[i] = j; else      nextval[i] = nextval[j];    } else    j = nextval[j];  }}int kmp(string s, string t, int pos) {  int l1 = s.length();  int l2 = t.length();  int nextval[255];  get_nextval(t, nextval);  int i = pos;  int j = 0;  while (i < l1&&j  {    if (j==-1||s[i] == t[j])     {      i++;      j++;    } else    j = nextval[j];  }  if (j ==l2)  return i - l2; else  return -1;}void main() {  string s, t;  int pos;  cout << "請(qǐng)輸入主句"<<endl;  cin >> s;  cout << "請(qǐng)輸入查找句"<<endl;  cin >> t;  cout << "請(qǐng)輸入從哪一個(gè)字符開(kāi)始查找（第一個(gè)字符的位置為0）"<<endl;  cin >> pos;  cout << "查找句位于" << kmp(s, t, pos);}

如果你對(duì)該篇文章存在任何疑問(wèn)

歡迎提出您的建議

E-meal：[email protected]

?掃碼關(guān)注我們