算法: KMP

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
56
public static int kmpMatch(String source, String key) {
// 生成next数组
int[] next = getNext(key);
int result = -1;
// 两个数组指针
int sLocation = 0;
int kLocation = 0;
while (sLocation < source.length()) {
// 如果两个字符相等了
if (key.charAt(kLocation) == source.charAt(sLocation)) {
if (kLocation == key.length() - 1) {// key的最后一个字符. 说明匹配完成
result = sLocation - key.length() + 1;
break;
} else {// 继续向后匹配
kLocation++;
sLocation++;
}
} else { // 两个字符不相等
if (kLocation == 0) { // 没有上一个匹配的字符, 继续往后匹配source
sLocation++;
} else { // key指针跳到上一个匹配的字符对应的next值
kLocation = next[kLocation - 1];
}
}
}
return result;
}

private static int[] getNext(String key) {
int[] result = new int[key.length()];
for (int i = 0; i < key.length(); i++) {
// 自身与前缀子字符串
String prefix = key.substring(0, i + 1);
result[i] = getNextValue(prefix);
}

return result;
}

private static int getNextValue(String str) {
int value = 0;
// 用于去重
Set<String> prefixes = Sets.newHashSet();
for (int i = 0; i < str.length() - 1; i++) {
// 前缀子字符串
String prefix = str.substring(0, i + 1);
prefixes.add(prefix);
}
for (int i = 0; i < str.length() - 1; i++) {
// 后缀子字符串
String prefix = str.substring(str.length() - 1 - i, str.length());
// 判断是否有相同的子串在set中, 如果有重复的, 就更新结果.
value = prefixes.add(prefix) ? value : Math.max(value, prefix.length());
}
return value;
}