单模式串字符串匹配

给定单个字符串S(长度m),查找目标模式串pattern(长度n)。 这个问题常见的会是采用朴素匹配,

朴素匹配实际为暴力匹配(BrueForce)本文讲述的是KMP算法, 维基百科 维基百科里面讲述的较详细, 就如下几个重点本文讲述下。

KMP相对朴素匹配

本质上是在朴素匹配上做了一个剪枝, 朴素匹配在S串上依次对pattern串进行比较,复杂度O(m*n), 而KMP逻辑会进行跳过,复杂度O(m+n)。

KMP关键点

  • 理解字符串的真前缀(proper preffix)、真后缀(proper suffix)。不包含本身的前缀或者后缀,如snake的真前缀s,sn,sna,snak。
  • 真前缀和真后缀的相同意味着什么,这个理解清楚了就是KMP对比跳过的剪枝逻辑。理解见代码
  • next()函数表及实现
  • 根据next()函数遍历目标串S

代码演示:

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class C10StrPattern {
/**
* 生成模式串next函数,函数作用为主串对比忽略比较的位置记录
* 表示的含义当前位置,真前缀和真后缀相同的个数, 正因为相同,所以已经比较过的可以根据这个信息直接跳到比较位置
* @param pattern 匹配模式串
* @return
*/
private static int[] genNextArray(String pattern) {
if (pattern == null || pattern.length() == 0) {
return new int[]{};
}
int[] result = new int[pattern.length()];
result[0] = 0;// 一个元素自己,真前、后缀相同个数为0
for (int i = 1; i < pattern.length(); i++) {
if (pattern.charAt(i) == pattern.charAt(result[i - 1])) { //当前元素和result记录值
result[i] = result[i - 1] + 1;
} else {
result[i] = 0;
}
}
return result;
}
/**
* @param str
* @param pattern
* @return ["1-4","6-9"]
*/
public static List<String> findPosition(String str, String pattern) {
List<String> result = new ArrayList<>();
if (str == null || pattern == null || str.length() == 0 || pattern.length() == 0) { // 不合理过滤
return result;
}
int[] next = genNextArray(pattern); // 生成next函数, 信息表
int i = 0, start = 0;
while (i < str.length()) {
for (int j = 0; j < pattern.length(); j++) {
if (i + j > str.length() - 1) { // 如果剩下的长度不符合直接退出后续查找
return result;
}
if (str.charAt(i + j) == pattern.charAt(j)) {
if (j == 0) { // j==0 并且i+j位置和 pattern串j位置相等,可能的起始位置记录
start = i;
}
if (j == pattern.length() - 1) {// 找到并且结束
result.add(String.format("%s-%s", start, i + j));
i++; // ** 注意此处从i+1开始继续,而不是当前找到的模式串结束位置
break;
}
} else { // ** 不相等 源串遍历索引i 直接跳到next() 位置。 加不加1 取决于next记录值, 有些实现next值默认-1,所以此处不用加1
i = i + next[j] + 1;
break;
}
}
}
return result;
}
public static void main(String[] args) {
//示例
//abababca 原始串S pattern串aba
//01234567 索引值
//00123401 next() 函数,剪枝跳跃的信息表
System.out.println(Arrays.toString(findPosition("abababca", "aba").toArray()));
}
}

代码文件:C10StrPattern.java

总结

  • “KMP关键点” 前两点是理解关键,后两点是实现
  • AC自动状态机本质来说是KMP的一个多模式演变, 多模串仅一个分支的话就是KMP

机器在于运动,大脑也需要不断思考运作才能避免秀逗


版权声明:本文为博主原创文章,未经允许不得转载。