KMP算法
28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
这种字符串匹配，常见两种算法，一个是BF，暴力算法，另一个是KMP算法，KMP算法难点就是求next数组（该数组保存回退的位置，利用真子串的特性，减少匹配的次数）
next数组
next[j] = k， 不同的j来对应一个K值，这个K就是将来要移动的j要移动的位置
求K的值的规则：
- 找到匹配成功部分的两个相等的真子串，一个下标从0开始，另一个以j-1下标结尾
- 不管什么数据next[0]=-1， next[1]=0
练习1：
a | b | a | b | c | a | b | c | d | a | b | c | d | e |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
-1 | 0 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 0 | 1 | 2 | 0 | 0 |
练习2：
a | b | c | a | b | c | a | b | c | a | b | c | d | a | b | c | d | e |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
-1 | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 0 |
问题：已知next[i]=k 如何求 next[i+1]?
因为长度相同：
- k-1-0 = i -1 - x
- x = i - k
可以推出：
p[0].....p[k-1] = p[i-k].....p[i-1]
如果：p[i] == p[k] -> next[i+1] = k+1 因为当上述成立：p[0]....p[k] == p[i-k].....p[i-1]
如果: p[i] != p[k] 那么 next[i+1] = ?
image.png
回退到的2号位置，不一定就是你要找的，继续回退，此时回退到了0下标处，一直回退去找：p[i] == p[k] -> next[i+1] = k+1
代码实现
BF
class Solution {
public:
int strStr(string haystack, string needle) {
int i=0, j=0;
while(i<haystack.size() && j<needle.size())
{
if(haystack[i]==needle[j])
{
i++;
j++;
}
else
{
i=i-j+1;
j=0;
}
}
if(j==needle.size())
{
return i-j;
}
return -1;
}
};
KMP
我写的错误版本，错误原因是，next数组求的有问题
class Solution {
public:
int strStr(string haystack, string needle) {
int i=0, j=0;
vector<int>next = getNext(needle);
int len1=haystack.size();
int len2=needle.size();
while(i<len1 && j<len2)
{
if(j == -1 || haystack[i]==needle[j])
{
i++;
j++;
}
else
{
j=next[j];
}
}
if(j==needle.size())
{
return i-j;
}
return -1;
}
vector<int> getNext(string str)
{
vector<int> next(str.size());
next[0]=-1;
if(str.size()==1)
return next;
next[1]=0;
for(int i=2; i<str.size(); i++)
{
int k = next[i-1];
if(str[i-1] == str[k])
{
next[i] = k + 1;
}
else
{
int j=i-1;
while(j>0 && str[j] != str[k]) //问题出在这里，这里应该是str[i-1]和str[k]相比
{
j = k;
k=next[j];
}
next[i] = k+1;
}
}
return next;
}
};
正确版本1
class Solution {
public:
int strStr(string haystack, string needle) {
int i=0, j=0;
vector<int>next = getNext(needle);
int len1=haystack.size();
int len2=needle.size();
while(i<len1 && j<len2)
{
if(j == -1 || haystack[i]==needle[j])
{
i++;
j++;
}
else
{
j=next[j];
}
}
if(j==needle.size())
{
return i-j;
}
return -1;
}
vector<int> getNext(string str)
{
vector<int> next(str.size());
next[0]=-1;
int k=0;
int i=1;
while(i<str.size()-1)
{
if(k==-1 || str[k]==str[i])
{
next[i+1]=k+1;
k++;
i++;
}
else
{
k=next[k];
}
}
return next;
}
};
正确版本2
class Solution {
public:
int strStr(string haystack, string needle) {
vector<int>next(needle.size());
next[0]=-1;
int i=1;
int k=0;
//已知next[i]求next[i+1]
// 两种情况：
// 1. needle[i] == needle[k] -> next[i+1] = k+1;
// 2. needle[i] != needle[k] -> 回退k，k=next[k]
while(i<needle.size()-1)
{
if(k==-1 || needle[i]==needle[k])
{
next[++i]=k+1;
k++;
}
else
{
k=next[k];
}
}
int j=0;
for(int i=0; i<haystack.size(); i++)
{
while(j>0 && haystack[i]!=needle[j])
{
j=next[j];
}
cout<< i<<" "<<j<<endl;
if(haystack[i]==needle[j])
{
j++;
}
if(j==needle.size())
{
return i-j+1;
}
}
return -1;
}
};
next数组优化
image.png
image.png
image.png
优化版本代码
class Solution {
public:
int strStr(string haystack, string needle) {
vector<int>next(needle.size());
next[0]=-1;
int i=1;
int k=0;
//已知next[i]求next[i+1]
// 两种情况：
// 1. needle[i] == needle[k] -> next[i+1] = k+1;
// 2. needle[i] != needle[k] -> 回退k，k=next[k]
while (i < needle.size() - 1)
{
if (k == -1 || needle[k] == needle[i])
{
next[i + 1] = k + 1;
if (needle[k+1] == needle[i+1])
{
if(needle[0] == needle[1])
{
next[1]=next[0];
}
next[i+1] = next[k+1];
}
k++;
i++;
}
else
{
k = next[k];
}
}
int j=0;
for(int i=0; i<haystack.size(); i++)
{
while(j>0 && haystack[i]!=needle[j])
{
j=next[j];
}
if(j==-1 || haystack[i]==needle[j])
{
j++;
}
if(j==needle.size())
{
return i-j+1;
}
}
return -1;
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2023-03-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录