题目描述
对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。
思路
KMP算法的典型应用
KMP的核心思想是要构造next数组。
next[i]的含义
target的第i个字符及其之前的字符组成的子字符串与从target头部开始匹配的字符个数
next数组的求法
初始化：next[0]=next[1]=0
next数组在字符串查找中，扮演了极其重要的角色。
- 当target[i]和source[j]不匹配时，不需要完全回退到target[0]重新开始比较，通过查找next数组，可以知道source[j-1]处已经匹配了多少个target字符，所以source[j]可以从其后的target字符开始比较，无需回退source，大大减少了重复比较的次数。
不用KMP的暴力比较，其时间复杂度是
O(source.length() * target.length())
KMP的时间复杂度是
O(source.length() + target.length())
此图帮助你理解KMP的思想：
代码
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
| private int[] next;
public int strStr(String source, String target) {
// 特殊情况处理
if(source == null || target == null) {
return -1;
}
if(target.equals("")) {
return 0;
}
// 预处理target字符串，得到next数组
kmpPreview(target);
int sourceIndex = 0;
int targetIndex = 0;
while(sourceIndex != source.length()) { // 如果访问完了source还未找到匹配，则不包含target
//对应字符相等的处理
if(source.charAt(sourceIndex) == target.charAt(targetIndex)) {
// target匹配成功
if(targetIndex == target.length()-1) {
return sourceIndex - target.length() + 1;
} else {
sourceIndex++;
targetIndex++;
}
} else { // 对应字符不等的处理
// 如果回退到target头部仍不相等，则放弃当前的进度，开始比较source的下一个字符
if (targetIndex == 0) {
sourceIndex++;
} else {
// 对应字符不等的处理，由next数组回退target下标，依然和当前的source对应的字符比较，利用了之前比较的进度
targetIndex = next[targetIndex];
}
}
}
// 不包含target
return -1;
}
/**
* @intention:构造next数组。next[i]表示s的第i个字符及其之前的字符组成的子字符串，与从s头开始完全匹配的字符个数
*/
private void kmpPreview(String s) {
next = new int[s.length()+1];
next[0] = 0;
next[1] = 0;
for(int i = 2; i <= s.length(); i++) {
if(s.charAt(i-1) == s.charAt(next[i-1])) {
next[i] = next[i-1] + 1;
} else {
next[i] = 0;
}
}
}
|
考差点