模式匹配的kmp算法(已改無錯字)
2022-09-14 13:40:10 本頁面
【正文】 模式字符串P，無論目標字符串T的取值是什么，均可應(yīng)用同一個失配函數(shù)對它匹配。例子 模式串P=”caatcat”,目標串T=”ctcaatcacaatcat”。第一次比較： T c t c a a t c a c a a t c a t P c a a t c a t第二輪比較： T c t c a a t c a c a a t c a t P c a a t c a t第三輪比較： T c t c a a t c a c a a t c a t P c a a t c a t第四輪比較： T c t c a a t c a c a a t c a t P c a a t c a t第一輪比較，模式串與目標串在第二個字符處發(fā)生匹配 。算法檢測到失陪后結(jié)束本輪比較，并且指針不發(fā)生回溯，仍指向失配位置。由于失配發(fā)生在第二個字符處，此時j=1，所以模式匹配P在下一輪匹配時的起始比較地址是P f(11)+1，即p0。第二輪比較中，由于模式字符串P所在的第一個字符處發(fā)生失配，此時j=0，所以讓目標的指針前進一位，模式的其實比較位置回到p0。接著進行第三輪比較。模式串P中的第7個字符發(fā)生失配，此時j=6。可知下一輪匹配的起始比較位置為P f(61)+1，即p2。目標指針不發(fā)生回溯，仍指向失配位置。接著進行第四輪匹配，第四輪匹配成功。 T c t c a
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1