网页制作的常用技术,做移动网站优化排名,seo完整教程视频教程,html5做网站的好处文章目录 KMP 算法基本概念next 数组含义及计算匹配过程 LeetCode-28.找到字符串中第一个匹配项的下标题目描述程序代码 KMP 算法
基本概念
S#xff1a;文本串P#xff1a;模式串next 数组#xff1a;next[i]表示当模式串中第 i 个字符与文本串中某个字符不匹配时#x… 文章目录 KMP 算法基本概念next 数组含义及计算匹配过程 LeetCode-28.找到字符串中第一个匹配项的下标题目描述程序代码 KMP 算法
基本概念
S文本串P模式串next 数组next[i]表示当模式串中第 i 个字符与文本串中某个字符不匹配时模式串应该跳到文本串的哪个位置继续匹配。
next 数组含义及计算
对于模式串Pnext[i]表示P[1 ... i-1]这个子串的最长相同前后缀的长度。也就是说如果P[i]与文本串S的某个字符不匹配那么我们可以将P向右移动next[i]个位置使得P[1 ... next[i]]与P[i-next[i] ... i-1]对齐继续比较P[next[i]]与S的下一个字符。这样可以避免重复比较已经匹配的部分提高效率。
next 数组的求法是通过模板串自己与自己进行匹配操作得出来的
// 计算next数组
for(int i 2; j 0; i m; i) {// 匹配不成功while(j 0 p[i] ! p[j1]) {j next[j];}// 匹配成功if(p[i] p[j1]) j;next[i] j;
}匹配过程
// 匹配
for(int i 1, j 0; i n; i) {// 匹配不成功while(j 0 s[i] ! p[j1]) {j next[j];}// 匹配成功if(s[i] p[j1]) j;// 匹配完成if( j m ) return i - m;
}LeetCode-28.找到字符串中第一个匹配项的下标
题目描述
给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标下标从 0 开始。如果 needle 不是 haystack 的一部分则返回 -1 。
程序代码
class Solution {
public:int strStr(string haystack, string needle) {int n haystack.size(), m needle.size();string s haystack;string p needle;vectorint next(m 1, 0);// 计算next数组for(int i 2, j 0; i m; i) {// 匹配不成功while(j 0 p[i] ! p[j1]) {j next[j];}// 匹配成功if(p[i] p[j1]) j;next[i] j;}// 匹配for(int i 1, j 0; i n; i) {// 匹配不成功while(j 0 s[i] ! p[j1]) {j next[j];}// 匹配成功if(s[i] p[j1]) j;// 匹配完成if( j m ) return i - m;}return -1;}
};
