KMP算法_vkmp18.top

作者：菜鸟追梦旅行 | 2024-04-19 09:05:58

踩

vkmp18.top

v KMP 算法的关键是求算模式串每个位置处的最长后缀与前缀相同的长度

v 假设当模式中第 j 个字符与主串中相应字符“失配”时，可以拿第 k 个字符来继续比较，则令 next[j]=k

v next 函数定义：

v 0 当 j=1 时

v next[j]= Max{k| 1<k<j 且’ p 1 …p k-1 ’= ‘p j-k+1 …p j-1 ’} 当此集合不空时

v 1 其他情况

v 思路：每当匹配过程中出现不相等字符时，不需回溯 i 指针，而是利用已经得到的“部分”匹配结果将模式向右“滑动”尽可能远的一段距离后继续进行比较。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/450951