KMP模式匹配算法-串的應用
前言
好久不見~各位看客老爺們，距離上次小向上班已經(jīng)過去了好久--TT，小向也不想，但是被一個地方卡住了好久，最近才弄清楚。那么廢話不多說，讓我們進入今天的主題叭~數(shù)據(jù)結構之串及其應用KMP模式匹配算法。還記得前段時間，小編參加英語考試，面對大量的生詞，小編人都嚇傻了，可是全部記憶一遍肯定來不及，記憶出現(xiàn)頻率最高的肯定是效率最快的，這件事情說起來很簡單，但是怎么才能知道什么單詞出現(xiàn)的頻率最高呢？這里面涉及到許許多多的東西，今天我們就不全部展開講解，不過，這里面最重要的其實就是去找一個單詞在一篇文章中的定位問題。即串的模式匹配。
什么是串？
下面讓我們來了解一下串。
雖然看到串的第一眼，大家可能有一點蒙的感覺，串？羊肉串？或者是別的balabala的東西。其實這里的串，指的是字符串。串：由零個或者多個字符組成的有限序列，又名叫字符串。一般我們把串記為s=”a1a2a3……an”,其中s是串的名稱，用雙引號或者單引號括起來的內容就是串的值，注意，在這個位置，雙引號不是串的內容。打個比方說，《靜夜思》“床前明月光，疑是地上霜。舉頭望明月，低頭思故鄉(xiāng)”，那么此時，《靜夜思》就是串的名稱，“床前明月光……”才是內容。
零個字符是什么意思呢？就是啥也沒有，這樣的串，我們又稱為空串，""直接這樣表示就可以了。他的長度為0.在串的定義中我們可以發(fā)現(xiàn)，串是有順序的，相鄰的字符之間有前驅和后繼的關系。并且串是有限的，一定要注意，串是有限的！下面再讓我們認識一個概念，主串，子串以及空格串。主串子串，其實很好理解，整個串的所有內容就是主串，而串中任意個數(shù)的連續(xù)字符組成的子序列稱為該串的子串。那空格串就更好理解了，就是只包含有限個空格的串，記住是有限個空格，可以不是一個，但是不可能是無限個?，F(xiàn)在再來看《靜夜思》，我們就知道了，整首古詩就是一個主串，而里面的每個句子或者每連續(xù)的幾個字，就是它的子串。
? 大致清楚了串的一些定義之后，我們來了解一下串的比較大小方式。對于兩個數(shù)來說，比較大小非常容易，2>1……。但是串怎么比較大小呢？其實串的比較大小方式大家猜應該也都可以猜出來，就是判斷他們挨個字母的前后順序。打一個比方來說，smart，stupid，他們的第一個字母都是s，認為不存在大小差異，而第二個字母，”m”字母在”t”字母之前，所以”m”<”t”.
但是事實上，對于計算機來說，他是不知道哪個字母在前哪個字母在后的，他是通過組成串的字符之間的編碼來進行的。現(xiàn)代計算機一般都是通過ASCII編碼，但是由于ASCII碼是用7位二進制表示一個字符，總共只能表示128個字符，所以擴展ASCII碼由8位二進制數(shù)表示一個字符，這樣就可以表示256個字符，滿足了大部分國家的需要?？墒?，對于我們國家那可是遠遠不夠的，我們國家除了漢語，還有土家語，蒙古語……等等語言，所以就有了現(xiàn)在的Unicode編碼，一般用16位的二進制數(shù)表示一個字符。
? ?那么現(xiàn)在我們就來正式的總結一下串的比較。
對于兩個長度相等的串來說，必須每個相應位置的字符都相等，才算是相等。即a1=b1,a2=b2,……，an=bn.
? 對于兩個長度不相等的串來說，s1=”a1a2……an”,s2=”b1b2……bm”,
? 如果n
? 對于n
? 大致的了解了串以后，本來是應該繼續(xù)介紹串的抽象數(shù)據(jù)類型和儲存結構，但是串的抽象數(shù)據(jù)類型和儲存結構和棧類似，這里就不多加敘述了。下面就讓我們進入串的應用部分，模式匹配算法。
樸素匹配算法
在剛開始的時候，我覺得寫一個查找單詞的程序很簡單，就依次來比較就行了。過程在這里給大家進行簡單的介紹。
? 對于一個主串s=“annyainy”，我們需要查找子串t=””yibeizi”.我最開始的思路是依次進行匹配。
? 主串s從第一位開始，s和t第一個字母不匹配，那么將s2和t1進行比較，依次類推，直到最后匹配成功。簡單的說，就是對主串的每一個字符作為子串開頭，與待匹配的字符串進行匹配。對主串做大循環(huán)，每個字符開頭做T的長度的小循環(huán)，直到匹配成功或全部遍歷完成為止。
? 下面給出相應的代碼
那么現(xiàn)在一個簡單的匹配代碼我們已經(jīng)寫出來了，但是這是最簡單的，也是最慢的。現(xiàn)在讓我們來分析一下，如果每一次不成功的匹配都發(fā)生在串t的最后一個字符。舉一個例子，s為“aaaaaaaaaaaab”，t為“aaaaaaab”，那么需要每次匹配到最后我們才知道，原來不匹配。這樣的情況下，時間復雜度就是O（（n-m+1）*m）。int index（string s, string t,int pos){int i = pos;/ pos是指開始搜索的位置，即開始搜索時的下標int j = 0；/ 這是當前子串的下標while(i < s.length() && t < b.length()) / 只有當i小于等于主串長度且j小于等于子串長度時進行循環(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(); elsereturn 0;}
? 相信大家看到這樣分析下來肯定會說，這確實太麻煩了，甚至難以忍受，那么就讓我們來看看一種更高效的算法。由D.E.Knuth，J.H.Morris和V.R.Pratt發(fā)表的一個模式匹配算法，簡稱KMP算法。
KMP模式匹配算法
在最開始，我們先來看一個串，s=abcababcaaccda……，t=abcabz，他們在進行匹配的時候，匹配到第六位時發(fā)現(xiàn)不匹配，按照樸素匹配算法，他們會依次往前移動一位，再重新進行比較，即整個匹配過程我們是通過s的i的值的不斷回溯來進行，但是，我們知道，t的第一位和s的第一位肯定不匹配，依次類推，直到和s的4位開始比較，才算步入正軌，那么我們可不可以把這些很顯然不對的步驟刪掉，把那些肯定匹配的步驟跳過呢？對，基于這種觀點，大佬們提出了KMP算法來解決這些完全沒有必要的回溯。
? 如果i的值不回溯，也就是大小不能發(fā)生變化，那么要考慮的變化就是j的值了。通過對樸素匹配算法的觀察，我們可以發(fā)現(xiàn)，要確定j值的變化，其實我們只要將當前j所在的位置和前面進行比較，如果出現(xiàn)了相同的字符，那么j的變化也會不一樣，也就是說，j值的變化只取決于自身而不取決于主串。
? 再拿上面的例子來說，t=abcdef，當中沒有任何重復的字符，那么j就從6變?yōu)?，如果t=abcabz，當匹配到z的時候，發(fā)現(xiàn)不匹配，此時j就從6變?yōu)?，而不是1，因為前綴”ab”和z之前的后綴”ab”是相等的。由此我們就可以知道j的值取決于當前字符之前的串的前后綴的相似度。
如果把t串的各個位置的j值變化定義為一個數(shù)組next，那么數(shù)組next的長度就是t串的長度，于是我們就可以得到下面的函數(shù)定義。
這里我們需要先明確一個概念，前綴和后綴。對于子串a(chǎn)cesdz來說，當j=5時，他的去掉第五個字符的子串是“aces”，前綴就是去掉再最后一個字符“s”，依次的子串，即a,ac,ace，那么后綴也很清楚了，去掉最前面一個，即s,es,ces.
? 那么next數(shù)組是怎么推導的呢？對于子串a(chǎn)cesdz
1）當j=1時，next[1]=0.
2）當j=2時，j由1到j-1就只有字符“a”,屬于其他情況next[2]=1.
3）當j=3時，j由1到j-1的串就是“ac”，顯然“a”和”c”不等，屬于其他情況，next[3]=1.
4）以此類推，最終next[j]為011111.
對于子串a(chǎn)ecaex
1）當j=1時，next[1]=0.
2）當j=2時，next[2]=1.
3）當j=3時，next[3]=1.
4）當j=4時，next[4]=1.
5）當j=5時，next[5]=2.
6）當j=6時，next[6]=3.
? ? ?我們根據(jù)經(jīng)驗就可以知道，如果前后綴一個字符相等，那么next[j]=1+1，n個字符相等就是next[j]=1+n.
? ? ?下面我們給出next數(shù)值推導的代碼，
void get_next(string t, int* next){int i = 1;int j = 0;next[1] = 0;while(i < t[0])/*在這個位置t[0]表示t的長度*/{if(j == 0 || t[i] == t[j]){++i;++j;next[i] = j;}elsej = next[j];}}
? ? 下面給出具體的匹配過程的代碼
/*此處s為主串，t為子串，pos為剛開始匹配的位置*/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];elsereturn 0;}
? ? ?KMP算法的時間復雜度是O(n+m），相比較樸素匹配算法來說是快了很多，但是這種優(yōu)勢只體現(xiàn)在重復部分很多的情況，否則差異不明顯。下面讓我們來看看KMP算法的進一步優(yōu)化。
KMP的改良
?如果主串為s=aaaacde,子串為t=aaaaaz，next[j]=012345，i=5,j=5時，發(fā)現(xiàn)不匹配，此時j變?yōu)?，仍然不匹配，然后變成3，依然不匹配，后面肯定也是一樣的不匹配，因為都是a，那么其實這些匹配都是不必要的，可以省去。那么我們完全可以用第一位的a的next數(shù)值來代替后面a的next數(shù)值，因此我們對next進行了改良。
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; elsenextval[i] = nextval[j];}}}
? 匹配算法和之前的是一樣的這里就不再重復。這里nextval的推導就也不重復了，和next的推導過程大致相同。
KMP的再改良
? ? 雖然介紹完了KMP算法的標準形式，但是，我發(fā)現(xiàn)在實際的操作中，有一些方面并不是很好操作，比如t[0],s[0]為字符串的長度，這里就需要進行一些別的操作實現(xiàn)，s[0],t[0]為字符串長度，麻煩了。在最后給出我在后面改進的KMP改良算法。希望大家在前面的內容看明白以后，來看看這個改良版本的算法。
using 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; elsenextval[i] = nextval[j];} elsej = 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++;} elsej = nextval[j];}if (j ==l2)return i - l2; elsereturn -1;}void main(){string s, t;int pos;cout << "請輸入主句"<<endl;cin >> s;cout << "請輸入查找句"<<endl;cin >> t;cout << "請輸入從哪一個字符開始查找（第一個字符的位置為0）"<<endl;cin >> pos;cout << "查找句位于" << kmp(s, t, pos);}
???快過年了，小編在這里給各位看客老爺們提前說一聲，祝大家新年快樂！
如果你對該篇文章存在任何疑問
歡迎提出您的建議
E-meal：[email protected]
?掃碼關注我們