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]?
因为长度相同：
- 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] = ?
回退到的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数组优化
优化版本代码
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;
}
};
|
微信
支付宝
