c++ 实现KMP算法

KMP KMP算法解决的问题 字符串str1和str2,str1是否包含str2,如果包含返回str2在str1中开始的位置。 如何做到时间复杂度O(N)完成? 思路: 首先判断两个字符串是否为空串,并且str2的长度是否小于str1的长度,因为题目要求str1中包含str2。 以上都满足的情况下,首先定义两个变量分别为 x ,y 作为后续字符串中字符遍历的下标,然后再生成一个vector容器next,用来后续的匹配加速 然后在str2中,做加速操作,也就是 看当前 i – 1和之前的所有字符,有没有相同的,最大匹配长度。 从上图可以看到,下标0和1位置的值永远都是固定的-1和0,。 x 字