主串與模式串的匹配

（1）BF算法：

　　　　　　BF算法比較簡單直觀，其匹配原理是主串S.ch[i]和模式串T.ch[j]比較，若相等，則i和j分別指示串中的下一個(gè)位置，繼續(xù)比較后續(xù)字符，若不相等，從主串S的下一個(gè)字符（i=i-j+2）起再重新和模式串T的第一個(gè)字符（j=1）比較。

?

（2）KMP算法：

　　　　　　KMP算法相對BF會(huì)復(fù)雜一些，但對于計(jì)算機(jī)而言，這其實(shí)是減少很多不必要的匹對。在匹配失敗時(shí)最大的移動(dòng)模式串，以減少匹配次數(shù)，即當(dāng)匹配失敗時(shí)（S.ch[i]!=T.ch[j]），在模式串中已匹配的字符找出其長度最長的相同前后綴，假設(shè)其長度為k，則模式串T回溯到T.ch[k+1]與S.ch[i]匹對。

模式串	前后綴	相同個(gè)數(shù)
a	無	0
ab	無	0
aba	a	1
abab	a、ab	2
ababa	a、ab、aba	3

在作業(yè)題中，我用的是KMP算法進(jìn)行匹配。考慮的當(dāng)模式串第一位字符與主串字符不匹配時(shí)，若按原方法回溯會(huì)陷入死循環(huán)，所以講next[0]初始為-1? ??

?

定義晚next函數(shù)后則定義KMP函數(shù)，僅需匹配時(shí)i++和j++，不匹配時(shí)i不變，j=next[j]（將模式串回溯至k）重新開始進(jìn)行匹配，直至匹配完成輸出i-j+1（主串中的子串的第一個(gè)字符所在位置）

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/llhs/p/10703167.html

總結(jié)

以上是生活随笔為你收集整理的主串与模式串的匹配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。