ky3-串-數(shù)據(jù)結(jié)構(gòu)考研課件-大連海事大學(xué)

1、第四部分第四部分 字符串字符串制作人：榮譽(yù) BFBF算法設(shè)計思想：算法設(shè)計思想：將主串的第將主串的第pospos個字符和模式的第個字符和模式的第1 1個字符比較，個字符比較， 若若相等相等，繼續(xù)逐個比較后續(xù)字符；，繼續(xù)逐個比較后續(xù)字符； 若若不等不等，從主串的下一字符（，從主串的下一字符（pos+1pos+1）起，重新與第一個字符比較。）起，重新與第一個字符比較。 BF算法算法 （又稱古典或經(jīng)典的、樸素的、窮舉的）（又稱古典或經(jīng)典的、樸素的、窮舉的） KMP算法算法（特點(diǎn)：速度快）（特點(diǎn)：速度快）算法算法種類：種類：直到主串的一個連續(xù)子串字符序列與模式相等直到主串的一個連續(xù)子串字符序列與模式相

2、等 。返回值為。返回值為S S中與中與T T匹配的子匹配的子序列序列第一個字符的序號第一個字符的序號，即匹配成功。，即匹配成功。否則，匹配失敗，返回值否則，匹配失敗，返回值 0 .0 .S=a b a b c a b c a c b a bT=T=a b c a cpos=5Int Index(SString S, SString T, int pos) i=pos; j=1; while ( i=S0 & jT0) return i-T0; /子串結(jié)束，說明匹配成功子串結(jié)束，說明匹配成功 else return0;/Index BFBF算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)即即IndexIndex（）操作的實(shí)

3、現(xiàn)（）操作的實(shí)現(xiàn) （見教材（見教材P79P79） S=a b a b c a b c a c b a bT=T=a b c a cpos=5相當(dāng)于子串向右滑動一個字符位置相當(dāng)于子串向右滑動一個字符位置匹配成功后指針仍要回溯！因?yàn)橐祷氐氖潜黄テヅ涑晒笾羔樔砸厮荩∫驗(yàn)橐祷氐氖潜黄ヅ涞氖讉€字符位置。配的首個字符位置。i ij j20132013年真題：年真題：KMPKMP算法是模式匹配算法算法是模式匹配算法KMP算法由兩部分組成：第一部分，計算模式串的next或nextval數(shù)組。第二部分，利用計算好的模式串的nextval數(shù)組，進(jìn)行模式匹配。 KMP算法中有next數(shù)組和nextval數(shù)組

4、之分。 他們代表的意義和作用完全一樣，完全可以混用。 唯一不同的是，next數(shù)組在一些情況下有些缺陷，而nextval是為了彌補(bǔ)這個缺陷而產(chǎn)生的。一、求解一、求解nextnext由上述公式，求模式串S1.j-1中,最大的匹配子串P1.Pk-1=Pj-k+1.Pj-1，其長度k-1，k就是nextj的值。例如，j=6時，abaab最大匹配串是ab=ab,長度2，所以next6=2+1=3算法：next思想： 求模式串的最大匹配串P1.Pk-1，是為了出現(xiàn)不匹配項時，j指針不用回溯到模式串的第一個元素(i指針不動)，只需回溯到j(luò)=nextj=k的位置繼續(xù)匹配。因?yàn)镻1.Pk-1=Pj-k+1.Pj

5、-1，所以P1.Pk-1和Sj-k+1.Sj-1不需要再比較了，一定相等。直接繼續(xù)比較Sj和Pk就可以了。next_val改進(jìn)的地方是aaad，j=3的位置，出現(xiàn)匹配失效，直接返回第1個比較，因?yàn)榍懊婢莂，一定不等，不必繼續(xù)比較了。next_val改進(jìn)的地方是：求求nextnext的算法的算法public static int next(char t)/ next函數(shù)求解 int i = 0, j = -1; int next = new intt.length; next0 = -1; while(i if(j = -1 | ti = tj) +i; +j; nexti = j; else

6、 j = nextj; 方法二方法二 求求nextnext步驟：next數(shù)組值的程序設(shè)計求解方法：首先可以肯定的是第一位的next值為0，第二位的next值為1，后面求解每一位的next值時，根據(jù)前一位 進(jìn)行比較。首先將前一位與其next值對應(yīng)的內(nèi)容進(jìn)行比較，如果相等，則該位的next值就是前一位的next值加上1；如果不等，向前繼續(xù)尋找next值對應(yīng)的內(nèi)容來與前一位進(jìn)行比較，直到找到某個位上內(nèi)容的next值對應(yīng)的內(nèi)容與前一位相等為止，則這個位對應(yīng)的值加上1即為需求的next值；如果找到 第一位都沒有找到與前一位相等的內(nèi)容，那么需求的位上的next值即為1。舉例：舉例：模式串 a b a a

7、b c a cnext值 0 1 1 2 2 3 1 2步驟參考步驟參考1.前兩位必為0，1。2.計算第三位的時候，看第二位b的next值，為1，則把b和1對應(yīng)的a進(jìn)行比較，不同，則第三位a的next的值為1，因?yàn)橐恢北鹊阶钋耙晃唬紱]有發(fā)生比較相同的現(xiàn)象。3.計算第四位的時候，看第三位a的next值，為1，則把a(bǔ)和1對應(yīng)的a進(jìn)行比較，相同，則第四位a的next的值為第三位a的next值加上1，為2。因?yàn)槭窃诘谌粚?shí)現(xiàn)了其next值對應(yīng) 的值與第三位的值相同。4.計算第五位的時候，看第四位a的next值，為2，則把a(bǔ)和2對應(yīng)的b進(jìn)行比較，不同，則再將b對應(yīng)的next值1對應(yīng)的a與第四位的a進(jìn)行

8、比較，相同，則第五位的next值為第二位b的 next值加上1，為2。因?yàn)槭窃诘诙粚?shí)現(xiàn)了其next值對應(yīng)的值與第四位的值相同。5.計算第六位的時候，看第五位b的next值，為2，則把b和2對應(yīng)的b進(jìn)行比較，相同，則第六位c的next值為第五位b的next值加上1，為3，因?yàn)槭窃诘谖逦粚?shí)現(xiàn)了其next值對應(yīng)的值與第五位相6.計算第七位的時候，看第六位c的next值，為3，則把c和3對應(yīng)的a進(jìn)行比較，不同，則再把第3位a的next值1對應(yīng)的a與第六位c比較，仍然不同，則第七位的next值為1。7.計算第八位的時候，看第七位a的next值，為1，則把a(bǔ)和1對應(yīng)的a進(jìn)行比較，相同，則第八位c的nex

9、t值為第七位a的next值加上1，為2，因?yàn)槭窃诘谄呶缓蛯?shí)現(xiàn)了其next值對應(yīng)的值與第七位相同。二、求解二、求解nextvalnextval值值求nextval數(shù)組值有兩種方法，一種是不依賴next數(shù)組值直接用觀察法求得，一種方法是根據(jù)next數(shù)組值進(jìn)行推理，兩種方法均可使用，視更喜歡哪種方法而定。 本文主要分析nextval數(shù)組值的第二種方法：模式串 a b a a b c a cnext值 0 1 1 2 2 3 1 2nextval值 0 1 0 2 1 3 0 2過程過程 1.第一位的nextval值必定為0，第二位如果于第一位相同則為0，如果不同則為1。2.第三位的next值為1，那

10、么將第三位和第一位進(jìn)行比較，均為a，相同，則，第三位的nextval值為0。3.第四位的next值為2，那么將第四位和第二位進(jìn)行比較，不同，則第四位的nextval值為其next值，為2。4.第五位的next值為2，那么將第五位和第二位進(jìn)行比較，相同，第二位的next值為1，則繼續(xù)將第二位與第一位進(jìn)行比較，不同，則第五位的nextval值為第二位的next值，為1。5.第六位的next值為3，那么將第六位和第三位進(jìn)行比較，不同，則第六位的nextval值為其next值，為3。6.第七位的next值為1，那么將第七位和第一位進(jìn)行比較，相同，則第七位的nextval值為0。7.第八位的next值為

11、2，那么將第八位和第二位進(jìn)行比較，不同，則第八位的nextval值為其next值，為2。 1.第一位的nextval值必定為0，第二位如果于第一位相同則為0，如果不同則為1。 2.第三位的next值為1，那么將第三位和第一位進(jìn)行比較，均為a，相同，則，第三位的nextval值為0。 3.第四位的next值為2，那么將第四位和第二位進(jìn)行比較，不同，則第四位的nextval值為其next值，為2。 4.第五位的next值為2，那么將第五位和第二位進(jìn)行比較，相同，第二位的next值為1，則繼續(xù)將第二位與第一位進(jìn)行比較，不同，則第五位的nextval值為第二位的next值，為1。 5.第六位的next

12、值為3，那么將第六位和第三位進(jìn)行比較，不同，則第六位的nextval值為其next值，為3。 6.第七位的next值為1，那么將第七位和第一位進(jìn)行比較，相同，則第七位的nextval值為0。 7.第八位的next值為2，那么將第八位和第二位進(jìn)行比較，不同，則第八位的nextval值為其next值，為2。模式串a(chǎn)baabcacnext值01122312nextval值01021302總結(jié)總結(jié) 求求nextvalnextval的算法：的算法：(1)第一位的nextval值必定為0，第二位如果于第一位相同則為0，如果不同則為1。(2)若si與s nexti 比較：不同，則nextvali值為其nex

13、t值;相同，則步驟（3）（3）s nexti 與s nexti nexti 比較:不同，則nextvali值為s nexti nexti 的next值;相同，若nextvali值為0時退出遞歸，則步驟（3）;三、三、nextnext和和nextvalnextval比較比較Next數(shù)組的缺陷舉例如下：比如主串是“aab.” 省略號代表后面還有字符。 模式串“aac”通過計算aac的next數(shù)組為012（另外，任何字符串的第二位字符的next總是1，因此你可以認(rèn)為他固定為1）當(dāng)模式串在字符c上失配時，會跳到第2個字符，然后再和主串當(dāng)前失配的字符重新比較，即此處用模式串的第二個a和主串的b比較即 a

14、ab aac顯然a也不等于b。然后 會跳到1，接著比，然后又失配，直到最后才使主串后移一位。而“aac”的nextval數(shù)組為002 當(dāng)在c失配時會跳到2，若還失配就直接跳到0，比next數(shù)組少比較了1次。在如果模式串很長的話，那可以省去很多比較，因此你應(yīng)該使用nextval數(shù)組。代碼實(shí)現(xiàn)代碼實(shí)現(xiàn) public static void main(String args) throws IOException/main函數(shù)，輸入主串和模式串 System.out.print(請輸入主串:); Scanner sn1 = new Scanner(System.in); String s1 = sn

15、1.next(); System.out.print(請輸入模式串:); Scanner sn2 = new Scanner(System.in); String s2 = sn2.next(); char s3 = s1.toCharArray(); char s4 = s2.toCharArray(); System.out.print(KMP_test(s3,s4); public static int KMP_test(char s, char t)/ 主串順序匹配 int next = next(t); int i = 0, j = 0; while(i if(j = -1 | si

16、 = tj) +i; +j; else j = nextj; System.out.println(i); if(j return 0; else return i-t.length; public static int next(char t)/ next函數(shù)求解 int i = 0, j = -1; int next = new intt.length; next0 = -1; while(i if(j = -1 | ti = tj) +i; +j; nexti = j; else j = nextj; System.out.println(Arrays.toString(next); return next; 對于改進(jìn)的對于改進(jìn)的KMPKMP算法，只需要把算法，只需要把nextnext函數(shù)換為函數(shù)換為nextvalnextval函數(shù)就行了函數(shù)就行了public static int next(char t) int i = 0, j = -1; int next = new intt.length; next0 = -1; while(i if(j = -1