??本篇講解串的有關知識，串就是字串，很常見，和線性表類似，但在基本操作上，通常以子串為操作物件，重點是字串的模式匹配演算法，就是在主串中找到子串，最經典的是KMP匹配演算法的原理，要知道演算法的原理及next陣列的推理程序，求next陣列可以先計算出部分匹配值表然后再變形，根據公式求解.改進方法是用nextval陣列，
一：簡單的模式匹配演算法
??子串的定位操作通常稱為串的模式匹配，求子串在主串中的位置，最簡單的定長存盤，是一種暴力的匹配演算法，代碼如下：
int Index(thisString S,thisSting T){
int i=1;j=1;
while(i<=S.length&&j<=T.length){
if(S.ch[i]==T.ch[j]){
i++;j++;
}
else{
i=i-j+2;
j=1;
}
}
if(j>T.length)
return i-T.length;
return 0;
}
??暴力匹配的最壞時間復雜度是O(nm)，其中n和m為主串和模式串的長度，但這種匹配演算法就會將主串前面匹配過的忽略掉，每次匹配失敗都是模式后移一位再從頭開始比較，比較重復，效率比較低，改進的演算法思路是如果已匹配相等的前綴序列中有某個后綴正好是模式的前綴，那么就可以將模式向后滑動到與這些字符對齊的位置，只針對模式子串進行操作，主串指標無需回溯，繼續進行比較，這種演算法僅與模式串本身結構有關，與主串無關，這種演算法也就是KMP演算法，下面進行詳細介紹這個演算法，
二：字串的前綴，后綴和部分匹配值
1.前綴
??前綴指除了最后一個字符以外，字串的所有頭部子串，
2.后綴
??后綴指除了第一個字符以外，字串的所有尾部子串，
3.部分匹配值
??部分匹配值為字串的前綴和后綴的最大相等公共前后綴長度，
比如在'ababa'中，'a'的最大相等公共前后綴長度為0，'ab'最大相等公共前后綴長度為0，依次可得所有子串的最大相等公共前后綴長度，然后就得到部分匹配值為00123，但是部分匹配值有什么作用呢，有一個公式是當某個字符匹配失敗時，
可以根據移動位數=已匹配的字符數-對應的部分匹配值(指的是已匹配的字符組的最后一個字符的部分匹配值)，和就相當于把已匹配的字符數的最大相等公共前綴移到后綴的位置，
??這個程序珠串始終沒有回退，故KMP演算法可以在O(n+m)的時間數量級上完成串的模式匹配操作，大大提高了匹配效率，
??當某趟發生失配時，對應的部分匹配值為0，此次移動的位數最大，直接將子串首字符移動到主串i位置進行下一趟比較，否則有最大相等公共前后綴長度，移動后從i位置進行比較，無論部分匹配值是否為0，都是從主串的第i個位置進行比較，
三：KMP演算法具體實作程序
??由上可知，KMP演算法的核心就是匹配失敗后移動子串的位置，可以認為是子串右移位數進行下一次比較，
??右移位數就是把已匹配的字符數的前綴移動到后綴的位置，也就是
??右移位數=已匹配的字符數-對應的部分匹配值(指的是已匹配的字符組的最后一個字符的部分匹配值)
??即Move = (j-1) - PM[j-1]
??每次匹配失敗后，都要找它前一個元素的部分匹配值，這樣使用起來就有些不方便，所以將PM表后移一位，這樣哪個元素匹配失敗，直接看它的部分匹配值即可，這時候要注意兩個細節：
??(1)第一個元素后移后空缺的位置用-1填充，因為若是第一個元素匹配失敗，則需要將子串向右移動一位，不需要計算移動的位數，
??(2)最后一個元素在右移的程序中溢位，他的部分匹配值是下一位元素使用的，但顯然已沒有下一個元素，故可以舍去，
??這樣就可以把右移位數運算式寫為如下：
??右移位數=已匹配的字符數-對應的部分匹配值(子串失配位置的匹配值)
??Move = (j-1) - next[j]
??然后子串的比較指標就回退到：
??j = j - Move = next[j] + 1
??這就是失配時字串的比較指標回退的位置，最終得到j=next[j]，含義是當子串的第j個元素失配時，則跳到子串的next[j]位置重新與主串當前位置進行比較，
四：求得next[j]陣列
??核心就是得到子串的最大公共前后綴，然后把子串最大公共前后綴的前綴根主串和子串的最大公共前后綴相同的元素對其，再從主串的第i個位置進行比較，
??當模式串已匹配字符序列中不存在最大公共前后綴時，應移動最大位數即j-1位，讓主串的第i個字符和模式第一個字符進行比較，此時右移位數最大，
??當模式串第一個字符與主串的第i個字符失配時，規定next[1]=0，可以認為是主串第i個位置和模式串第一個字符的前面空位置對齊，直接將模式串后移，從主串的下一個位置(i+1)和模式串的第一個字符繼續比較，這樣可以得到next函式公式如下：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/122752.html
標籤：其他
上一篇：努力告別游戲