数据结构––kmp算法(串)
kmp算法作为串的一个重要内容，必然有一定的难度，而在看到各类教辅书里的概念与解释后，其晦涩难懂的内容直接劝退一部分人，现在，让我们来看看吧
KMP解决的问题类型
KMP算法的作用就是在一个已知的字符串中查找子串的位置，就是串的匹配模式。比如，主串a = “cabcabcde”，子串b = “ab”。而我们就是要在a中找b的位置，那么这么看来是很简单的，但是，如果是字符串很长的时候呢？这样找起来就很麻烦了。接下来就介绍2种方法。
方法一：暴力求解法（BF算法）
从主串a和子串的第一个字符开始，将2个字符串的字符一一匹配，如果不匹配，主串就从第二个字符，子串从第一个字符开始再次匹配，如果不匹配，就从主串第三个字符，子串第一个字符开始。
那么，暴力求解法为什么这么慢呢？因为回溯的次数太多了
方法二：
每一个字符前的字符串都有最长相等前后缀，而且最长相等前后缀的长度是我们移位的关键，所以我们单独用一个next数组存储子串的最长相等前后缀的长度。而且next数组的数值只与子串本身有关。
所以next[i]=j,含义是：下标为i 的字符前的字符串最长相等前后缀的长度为j。
我们可以算出，子串t= "abcabcmn"的next数组为next[0]=-1(前面没有字符串单独处理)
原文地址：https://blog.csdn.net/2301_80190473/article/details/137873707
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！