那个网站可以免费建站,单位建网站的优势,北京网站建设技术部,北京网站建设hj华网天下1理解next数组定义#xff1a;最长相等前后缀#xff08;不含当前字符并且不能是整体#xff09;
算法讲解100【扩展】 KMP算法原理和代码详解_哔哩哔哩_bilibili
next数组的值#xff1a;假设这个i出现了不匹配就从next[i]的位置开始在再匹配
2next数组生成 看一下是怎…1理解next数组定义最长相等前后缀不含当前字符并且不能是整体
算法讲解100【扩展】 KMP算法原理和代码详解_哔哩哔哩_bilibili
next数组的值假设这个i出现了不匹配就从next[i]的位置开始在再匹配
2next数组生成 看一下是怎么跳的算法讲解100【扩展】 KMP算法原理和代码详解_哔哩哔哩_bilibili
为什么这么跳算法讲解100【扩展】 KMP算法原理和代码详解_哔哩哔哩_bilibili
next代码算法讲解100【扩展】 KMP算法原理和代码详解_哔哩哔哩_bilibili #includeiostream
#includevector
#includealgorithm
#includestring
using namespace std;vectorint fun_next(string str1) //next生成
{vectorintnext(str1.size());next[0] -1;next[1] 0;int i 2, cn 0;while (i str1.size()){if (str1[i - 1] str1[cn])next[i] cn; else if (cn 0) //一次不成功cn还可以往前跳 。cn为0说明没有前后缀下一个就是0了 cn next[cn]; else next[i] 0;}return next;
}int main()
{string str1(abcabc);string str2(afdfabcabcghj);vectorintnext fun_next(str1);for (auto i : next)cout i ;cout endl;int m str1.size(), n str2.size();int i 0, j 0;while (i m j n) //匹配{if (str1[i] str2[j]){i; j;}else if (i 0)j;elsei next[i];}if (i m)cout 找到了: j - i;elsereturn -1;return 0;
}
