题目描述
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。
-
示例 1:
输入:haystack = "sadbutsad", needle = "sad"
输出:0
解释:"sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。 -
示例 2:
输入:haystack = "leetcode", needle = "leeto"
输出:-1
解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。 -
提示:
1 <= haystack.length, needle.length <= 104 haystack 和 needle 仅由小写英文字符组成
KMP算法
字符串匹配问题,设主串有m个字符,模式串有n个字符,暴力方法要时间O(mn)。KMP算法通过求解next数组,消除了失配时主串回溯步骤,使得时间复杂度降低到O(m+n)。
核心 —— next/nextval数组
当haystack[p]和needle[q]失配发生时,主串指针p不动,模式串指针q跳转到nextval[q]与主串匹配。
分析模式串,求解next/nextval数组
-
先求next数组
next[i] = needle[0..i]的最长匹配前后缀的长度;
-
推导nextval数组
nextval[0] = -1;
nextval[i] = next[i-1]; -
也可以一步到位,比如这个实现
vector<int> nextval(n, 0); nextval[0] = -1; // -1表示下一匹配中,主串指针p++, 模式串指针q=0 for(int j = 0, k = -1; j < n - 1; ) { if(k == -1 || needle[j] == needle[k]) { ++k, ++j; nextval[j] = k; } else { k = next[k]; // point } }
匹配,返回第一次匹配模式串的下标
int p = 0, q = 0;
while(q < n && p < m) {
if(haystack[p] == needle[q]) {
++p, ++q;
} else {
if(nextval[q] == -1) {
++p;
q = 0;
} else {
q = nextval[q];
}
}
}
if(q == n) {
return p - n;
} else {
return -1;
}
标签:匹配,nextval,0028,needle,next,KMP,下标,haystack,LeetCode
From: https://www.cnblogs.com/GaogaoBlog/p/18394816