字符串匹配问题又称模式匹配（pattern matching）。该问题可以概括为「给定字符串 S 和 T，在主串 S 中寻找子串 T 」。字符 T 称为模式串 (pattern)。
暴力做法 BF
简称 BF (Brute Force) 算法。该算法的基本思想是从主串 T 的第一个字符开始和模式串 T 的第一个字符进行比较，若相等，则继续比较二者的后续字符；否则，模式串 T 回退到第一个字符，重新和主串 S 的第二个字符进行比较。如此往复，直到 S 或 T 中所有字符比较完毕。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void bruteForce(String s, String p) {
int sLen = s.length();
int pLen = p.length();
for (int i = 0; i < sLen - pLen; i++) {
boolean flag = true;
for (int j = 0; j < pLen; j++) {
if (s.indexOf(i + j) != p.indexOf(j)) {
flag = false;
break;
}
}
if (flag) {
System.out.println(i);
}
}
}
|
设 n 为主串的长度，m 为模式串的长度。默认 m<=n。
- 最好的情况：匹配成功时，时间复杂度为 $O(n)$ ；匹配失败时，时间复杂度为 $O(m)$。
- 最坏的情况：每趟不成功的匹配都发生在模式串的最后一个字符，BF 算法要执行 m(n-m+1) 次比较，时间复杂度为 $O(mn)$。
KMP 算法
Knuth-Morris-Pratt 算法是一个著名的字符串匹配算法。
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
|
public class KMP1 {
private int[][] dp;
private String pat;
public KMP1(String pat) {
this.pat = pat;
int M = pat.length();
// dp[状态][字符] = 下个状态
dp = new int[M][256];
// base case
dp[0][pat.charAt(0)] = 1;
// 影子状态 X 初始为 0
int X = 0;
// 构建状态转移图（稍改的更紧凑了）
for (int j = 1; j < M; j++) {
for (int c = 0; c < 256; c++) {
dp[j][c] = dp[X][c];
dp[j][pat.charAt(j)] = j + 1;
// 更新影子状态
X = dp[X][pat.charAt(j)];
}
}
}
public int search(String txt) {
int M = pat.length();
int N = txt.length();
// pat 的初始态为 0
int j = 0;
for (int i = 0; i < N; i++) {
// 计算 pat 的下一个状态
j = dp[j][txt.charAt(i)];
// 到达终止态，返回结果
if (j == M) {
return i - M + 1;
}
}
// 没到达终止态，匹配失败
return -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
|
public class KMP {
/** 在文本 text 中寻找模式串 pattern，返回所有匹配的位置开头 */
public List<Integer> search(String text, String pattern) {
List<Integer> positions = new ArrayList<>();
int[] maxMatchLengths = calculateMaxMatchLengths(pattern);
int count = 0;
for (int i = 0; i < text.length(); i++) {
while (count > 0 && pattern.charAt(count) != text.charAt(i)) {
count = maxMatchLengths[count - 1];
}
if (pattern.charAt(count) == text.charAt(i)) {
count++;
}
if (count == pattern.length()) {
positions.add(i - pattern.length() + 1);
count = maxMatchLengths[count - 1];
}
}
return positions;
}
/** 构造模式串 pattern 的最大匹配数表 Partial Match Table */
private int[] calculateMaxMatchLengths(String pattern) {
int[] maxMatchLengths = new int[pattern.length()];
int maxLength = 0;
for (int i = 1; i < pattern.length(); i++) {
while (maxLength > 0 && pattern.charAt(maxLength) != pattern.charAt(i)) {
maxLength = maxMatchLengths[maxLength - 1];
}
if (pattern.charAt(maxLength) == pattern.charAt(i)) {
maxLength++;
}
maxMatchLengths[i] = maxLength;
}
return maxMatchLengths;
}
}
|
用 $O(m+n)$ 的时间以及 O(n) 的内存解决了该问题。
BoyerMoore
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
public class BoyerMoore {
public static void main(String[] args) {
String text = "here is a simple example";
String pattern = "example";
BoyerMoore bm = new BoyerMoore();
bm.boyerMoore(pattern, text);
}
public void boyerMoore(String pattern, String text) {
int m = pattern.length();
int n = text.length();
Map<String, Integer> bmBc = new HashMap<>();
int[] bmGs = new int[m];
// proprocessing
preBmBc(pattern, m, bmBc);
preBmGs(pattern, m, bmGs);
// searching
int j = 0;
int i = 0;
int count = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && pattern.charAt(i) == text.charAt(i + j); i--) { // 用于计数
count++;
}
if (i < 0) {
System.out.println("one position is:" + j);
j += bmGs[0];
} else {
j += Math.max(bmGs[i], getBmBc(String.valueOf(text.charAt(i + j)), bmBc, m) - m + 1 + i);
}
}
System.out.println("count:" + count);
}
private void preBmBc(String pattern, int patLength, Map<String, Integer> bmBc) {
System.out.println("bmbc start process...");
{
for (int i = patLength - 2; i >= 0; i--)
if (!bmBc.containsKey(String.valueOf(pattern.charAt(i)))) {
bmBc.put(String.valueOf(pattern.charAt(i)), (Integer) (patLength - i - 1));
}
}
}
private void preBmGs(String pattern, int patLength, int[] bmGs) {
int i, j;
int[] suffix = new int[patLength];
suffix(pattern, patLength, suffix);
// 模式串中没有子串匹配上好后缀，也找不到一个最大前缀
for (i = 0; i < patLength; i++) {
bmGs[i] = patLength;
}
// 模式串中没有子串匹配上好后缀，但找到一个最大前缀
j = 0;
for (i = patLength - 1; i >= 0; i--) {
if (suffix[i] == i + 1) {
for (; j < patLength - 1 - i; j++) {
if (bmGs[j] == patLength) {
bmGs[j] = patLength - 1 - i;
}
}
}
}
// 模式串中有子串匹配上好后缀
for (i = 0; i < patLength - 1; i++) {
bmGs[patLength - 1 - suffix[i]] = patLength - 1 - i;
}
System.out.print("bmGs:");
for (i = 0; i < patLength; i++) {
System.out.print(bmGs[i] + ",");
}
System.out.println();
}
private void suffix(String pattern, int patLength, int[] suffix) {
suffix[patLength - 1] = patLength;
int q = 0;
for (int i = patLength - 2; i >= 0; i--) {
q = i;
while (q >= 0 && pattern.charAt(q) == pattern.charAt(patLength - 1 - i + q)) {
q--;
}
suffix[i] = i - q;
}
}
private int getBmBc(String c, Map<String, Integer> bmBc, int m) {
// 如果在规则中则返回相应的值，否则返回pattern的长度
if (bmBc.containsKey(c)) {
return bmBc.get(c);
} else {
return m;
}
}
}
|