kmp算法,可以加快找字串位置的速度。
为什么加快呢,因为在每次比较过程中,找到了模式串对称的小串,然后直接移过去。
比如,主串abcabcabe,模式串abcabe。
第一次,匹配到主串的第二个c,失败,然后根据前面串的对称串ab,
第二次首先匹配第二个ab的首位置。
我的疑问是,跳过中间的字符匹配,会不会造成误差呢?比如少了些匹配成功的机会
不会。跳过去的是前缀肯定不符合的,它肯定不能构成模式串
不会的 kmp是尽可能多的移动 他会根据目前匹配的信息给你进行移动 就好比你说的ab 肯定是先跳转到下一个ab其他的串不满足你小串跳过了不会有任何影响