使用kmp算法實現(xiàn)一個模式匹配(編輯修改稿)
2025-07-14 05:41 本頁面
【文章內(nèi)容簡介】 j==0||t[i]==t[j]) { i++。 j++。 next[i]=j。 } else j=next[j]。 } } 模式匹配KMP算法的實現(xiàn)KMP算法的思想：主串s，模式t希望某趟在si和tj匹配失敗后，指針i不回溯，模式t向右“滑動”至某個位置上，使得tk 對準(zhǔn) s i 繼續(xù)向右進行。顯然，現(xiàn)在問題的關(guān)鍵是串t“滑動”到哪個位置上？不妨設(shè)位置為k，即si和tj匹配失敗后，指針i不動，模式t向右“滑動”，使tk和si對準(zhǔn)繼續(xù)向右進行比較，要滿足這一假設(shè)，就要有如下關(guān)系成立：＂t1 t2 … tk1 ＂ =＂sik+1 sik+2 … si1 ＂ ()式左邊是tk前面的k1個字符，右邊是si 前面的k1個字符。而本趟匹配失敗是在si和tj之處，已經(jīng)得到的部分匹配結(jié)果是：＂t1 t2 … tj1 ＂ =＂sij+1 sij+2 … si1 ＂（）因為kj，所以有：＂tjk+1 tjk+2 … tj1 ＂ =＂sik+1 sik+2 … si1 ＂ ()式左邊是 tj前面的k1個字符，右邊是si 前面的k1個字符，通過()和()得到關(guān)系：＂t1 t2 … tk1 ＂ =＂tjk+1 tjk+2 … tj1 ＂ ()結(jié)論：某趟在si和tj匹配失敗后，如果模式串中有滿足關(guān)系(4)的子串存在，即：模式中的前k1個字符與模式中tj字符前面的k1個字符相等時，模式t就可以向右“滑動”至使tk和si對準(zhǔn)，繼續(xù)向右進行比較即可。在求得模式的next函數(shù)之后，匹配可如下進行：假設(shè)以指針i和j分別指示主串和模式中的比較字符，令i的初值為pos，j的初值為1。若在匹配過程中si≠tj，則i和j分別增１，若si≠tj 匹配失敗后，則i不變，j退到next[j]位置再比較，若相等，則指針各自增１，否則j再退到下一個next值的位置，依此類推。直至下列兩種
研究報告相關(guān)推薦
鄂ICP備17016276號-1