KMP算法及next数组的确定
KMP算法
暴力匹配算法,存在比较指针的回溯的问题,这就是造成这个简单的算法效率比较低的原因。而KMP算法则可以很好的避免(KMP算法仅仅移动模式串的位置,比较指针不回溯)。
KMP算法步骤:
-
首先,找到主串和模式串不匹配的位置。
-
直接移动模式串,使之前的前缀直接移动到原先的后缀的位置。
这样一来,比较指针所在的位置左边的串使匹配的。
说明:如果原串中有多个公共前后缀,一定要取最长的那一对。
- 继续后移比较指针,直到发现下一个不匹配的地方,或者直到模式串末尾,匹配成功。
判定匹配失败的情况:
移动模式串:
此时模式串超出主串的范围,可以判定匹配失败。
一些特殊情况:
若在匹配过程中,第一个位置或者第二个位置等就发生不匹配(无公共前后缀),则将主串前移一个位置比较(比较指针指向模式串的位置不变)
在此,我们引入next数组。
next数组的引入:
模式串:
假如六号位发生不匹配:
根据KMP算法,寻找最长公共前后缀长度,并移动:
按此步骤,这样,我们就可以得到所有位置上的描述。
将结果化成数字:
放到一个数组中:
这样,我门就得到了next数组。
假如10号位发生不匹配,则从模式串上的4号字符与主串当前位发生比较。
这样,这个数组就指示了,当发生不匹配时,下一步我们要干什么。这就叫next数组。
则从模式串上的4号字符与主串当前位发生比较。
这样,这个数组就指示了,当发生不匹配时,下一步我们要干什么。这就叫next数组。