建设银行论坛网站,企业网站的设计与实现,百度识图软件,做百度推广去些网站加客户可以参考https://www.bilibili.com/video/BV1AY4y157yL/kmp 主要做的就是子串匹配#xff0c;类似C程序的 strstr() 函数记录一下#xff0c;也防止我自己忘记传统暴力求解算法是源串 ssssssssa
子串 sssa#xff08;下面暴力求解#xff09;
先 (子串从 0 位置匹配#x…可以参考https://www.bilibili.com/video/BV1AY4y157yL/kmp 主要做的就是子串匹配类似C程序的 strstr() 函数记录一下也防止我自己忘记传统暴力求解算法是源串 ssssssssa
子串 sssa下面暴力求解
先 (子串从 0 位置匹配并且匹配到最后一个字符才发现不对白搞)
ssssssssasssa其次 (子串从 0 位置匹配并且匹配到最后一个字符才发现不对白搞)
ssssssssasssa再后面就是 (子串从 0 位置匹配并且匹配到最后一个字符才发现不对白搞)
ssssssssasssa效率不高kmp的算法出现就是为了解决这个问题kmp是由三位大佬发现的他们三人的名字首字母分别就是K、M、P有没有一种办法就是少做无用功在刚刚那个场景下先 a和c不匹配
ssssssssa
sssa其次(子串从 2 位置匹配)
ssssssssasssa然后(子串从 2 位置匹配)
ssssssssasssa.......最后
然后(子串从 2 位置匹配)匹配成功
ssssssssasssa从 2 位置匹配显然提高了匹配速度但是 2 位置是怎么知道的呢kmp 算法中就是先计算一个数组叫做 next这个next计算只需要子串然后next的作用是记录子串回溯的位置当源串和子串不匹配时不像上面那样老是回溯0子串 sssa
next数组 0120回溯的位置就是最长前缀的位置比如子串 abcabcd
next数组 ...1230
解释
1 是因为 aa
2 是因为前面已经有匹配字符 aa 了那么 现在刚好 bb就最长前缀就等于 1 的基础上加 1 等于 2
3 是因为前面已经有匹配字符 aa bb 了那么 现在刚好 cc就最长前缀就等于 2 的基础上加 1 等于 3
0 是因为d没有最长前缀为啥next是基于前缀因为比如我都匹配到最后一位d和a源串第七个不相等了由于前面有相似的前缀
源串 abcabcaeee
子串 abcabcd那么下一步就是 【子串a第四个和a源串第七个第七个刚刚没匹配上比就是因为前缀一样才敢让子串匹配位置不从0开始因为前面有相似的结构】
源串 abcabcaeee
子串 abcabcd特殊场景
子串 sssa
next数组 0120
解释
0 是因为s没有最长前缀
1 是因为 第二个s第一个s
2 是因为前面已经有匹配字符 ss 了那么 现在刚好 第三个s第二个s就最长前缀就等于 1 的基础上加 1 等于 2
下面需要结合底部计算next函数一起看子串 sssa
next数组 0120其实就是在计算前缀
计算next数组也是有两个下标计算建议对照下面代码看 i为遍历字符串的变量j为最长前缀的下标
首先 next[0] 肯定是等于0的第一个就不匹配那肯定回溯还是0
那么 next[1] 由于 str[i] str[j] 即 str[0] str[1]ss,前缀相同j自然
next[1]j即 next[1]1
由于本题是 sssa
所以会出现子串 sssa
next数组 012题外话我们知道a是在前面没有最长前缀的最后结果肯定为0
匹配到最后一位时我们发现跟前面不相等j就看看前面有没有相等的j2但是 str[2] 也不等于 a
然后while循环一直往前找最长前缀从2到1到0最终没找到为0但是比如子串 aaaab....aaaaa
next数组 01230....0123?(此时j为3i为n)?处 a和b不匹配jnext[j-1]即 jnext[3-1]即 j2,而str[2]str[n],j退出
next[n]3这里j没有从0开始快了一点其实从0开始也能算出3这个结果最终结果为
子串 aaaab....aaaaa
next数组 01230....01233上代码class Solution {
public:int strStr(string haystack, string needle) {// 计算nextvectorint next(needle.length(), 0);getNext(needle, next);// 匹配过程int j0;int i0;for(;ihaystack.length() jneedle.length();) {// 当前串匹配if (haystack[i]needle[j]) {j;i;} else {// 当前串不匹配if (j0)// 防止j一直卡在0死循环i;else// 当前串不匹配但是i的值不自增只改变j jnext[j-1];}}// 返回结果if (jneedle.length())return i-j;elsereturn -1;}void getNext(string str,vectorint next) {// j 从 0 开始 i 从 1 开始已知第一个 next[0] 一定是等于 0 的因为前面没有字符了for(int j0,i1;istr.length();i) {// 当前如果不匹配那就去看看它前一个的下标位置对应的字符是否匹配while (j 0 str[i] ! str[j]) {jnext[j-1];}// 当前如果匹配j 往前走if(str[i]str[j]) {j;}// j 走多远前缀最长就是多远next[i] j;}}
};
