在串的模式匹配中，KMP匹配算法是有用的办法，回答以下问题:①KMP算法的基本思想是什么?
答: KMP算法的思想是，设s为目标串、t为模式串，并设i指针和j指针分别指示目标串和模式串中待比较的字符，令i和J的初值均为0。若有[tex=2.143x1.214]GzYY57w3IPzOK8dsNiXvIg==[/tex], 则i和j分别增1:否则，i不变，j退回到j=next[j]的位置(即模式串右滑)，比较[tex=0.714x1.0]GHqarXBZbfD8we5eDUzsNg==[/tex]和[tex=0.714x1.214]EGCY9DMMXZ1JnaQ8B1I3ow==[/tex]若相等则指针各增1.否则j再退回到下一个j=next[j]的位置(即模式串继续右滑),再比较[tex=0.714x1.0]GHqarXBZbfD8we5eDUzsNg==[/tex]和[tex=0.714x1.214]EGCY9DMMXZ1JnaQ8B1I3ow==[/tex]依此类推，直到出现下列两种情况之一，一种情况是j退回到某个J=next[j]位置时有[tex=2.143x1.214]GzYY57w3IPzOK8dsNiXvIg==[/tex],则指针各增1后继续匹配;另一种情况是j退回到j=-1时，此时令i、j指针各增1,即下一次比较[tex=1.786x1.214]8ZE2wjk6nrzMVX/buOuETw==[/tex]和[tex=0.714x1.143]sVbwS2YSnAo0Vg94iZhw1A==[/tex] .
举一反三
内容
- 0
KMP算法的特点是在模式匹配时指示主串的指针（）。
- 1
KMP算法是无回溯的模式匹配算法
- 2
KMP算法是无回溯的模式匹配算法
- 3
KMP算法的特点是在模式匹配时指示主串的指针不会回溯
- 4
主串为’abaababaddecab’ ,模式串为’abad’。使用KMP算法需要（）次匹配成功。