求KMP算法 基本思想

题目

求KMP算法 基本思想

答案

(1)求得模式串中每个字符的next[j]值；
(2)进行模式匹配.
假设i和j分别为指示主串和模式串中正在比较的字符的当前位置,并对i 和j 赋初值0.在匹配的过程中,若si=tj,则i和j分别增加1,继续进行比较,否则,i不变,而j退回到next[j]的位置进行新一轮的比较.如此递推下去,直到出现下列两种情况：
当j退回到某个值next[j]值时,匹配成功,则i和j分别增加1继续匹配；
当j退回到值为0时,即next[j]=0,说明主串的当前字符匹配失败,这时将主串向右滑动一个位置,即从i+1处重新开始新一轮的匹配,此时j=0.