28. 找出字符串中第一个匹配项的下标 - 力扣(LeetCode)
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。
这种字符串匹配,常见两种算法,一个是BF,暴力算法,另一个是KMP算法,KMP算法难点就是求next数组(该数组保存回退的位置,利用真子串的特性,减少匹配的次数)
以第一个字符开始,当前字符为结尾
- 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串
- 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串
比如 aabaaf
长度为前1个字符的子串a,最长相同前后缀的长度为0
长度为前2个字符的子串aa,最长相同前后缀的长度为1
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]?
![image.png](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202303132035003.png)
因为长度相同:
- 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](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202303132048527.png)
回退到的2号位置,不一定就是你要找的,继续回退,此时回退到了0下标处,一直回退去找:p[i] == p[k] -> next[i+1] = k+1
代码实现
BF
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| 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数组求的有问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| 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]) { j = k; k=next[j]; } next[i] = k+1; } }
return next; } };
|
正确版本1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| class Solution { public: int strStr(string haystack, string needle) { vector<int>next(needle.size()); next[0]=-1; int i=1; int k=0; 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](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202303171525238.png)
![image.png](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202303171529695.png)
![image.png](https://cdn.jsdelivr.net/gh/atongrun/ImageHost@main/202303171533230.png)
优化版本代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| class Solution { public: int strStr(string haystack, string needle) { vector<int>next(needle.size()); next[0]=-1; int i=1; int k=0; 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; } };
|