前言
串结构是计算机程序中经常需要使用和运算的，深入研究其结构和相关算法是大有益处的。
串
串为一种特殊的线性表结构，所以可以用顺序表和链表的方式来进行实现，由于串结构的使用非常平凡，基本上是每个应用程序都会使用的一种结构，所以主流的编程语言都对字符串有非常良好的工具库支持，因此我们在这里不研究串结构的实现，我们会将重心放在字符串模式匹配算法和实现上。
字符串模式匹配
字符串模式匹配就是在主串中找到与模式串相同的子串，并返回其所在位置。模式串就是我们要在主串寻找字串，它不一定在主串中存在，而子串就是主串中的连续子集，子串是一定存在的，不要把模式串和子串的概念混淆了。
朴素模式匹配算法
朴素模式匹配算法其实就是暴力搜索。
假设主串长度为 n，模式串长度为 m，然后将主串中所有长度为 m 的子串依次与模式串对比，直到找到一个完全匹配的子串，或者所有子串都不匹配为止。
下面是代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int index(std::string s, std::string t) {
int sLen = s.length();
int tLen = t.length();
int i = 0, j = 0;
while (i < sLen && j < tLen) {
if (s[i] == t[j]) {
i++;
j++;
} else {
i -= j - 1;
j = 0;
}
}
if (j >= tLen) return i - tLen;
return -1;
}
|
这个算法的最坏时间复杂度为 O(nm)
KMP 算法
KMP 算法是基于朴素模式匹配算法优化的，从刚才的算法中我们不难看出，如果我们模式串的指针已经指向了最后一位，那么就证明前面的 m-1 个字符都是匹配上的，如果前面的 m-1 个字符存在最大公共前后缀，那么我们就没有必要像朴素匹配那样将主串的指针移动到下一个子串处和将模式串的指针移动到模式串头，而是只将模式串指针移动到最大公共前后缀的前缀处后面，主串指针保持不变。所以说通过构建一个部分匹配表 next 数组，我们可以实现 O（m+n）的匹配算法，其中 O（m）为构建 next 数组的时间，O（n）为匹配过程所花费的时间，这也就是大名鼎鼎的 KMP 算法（Knuth–Morris–Pratt algorithm）。
代码实现：
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
| public class KMP {
public static int[] buildNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
next[0] = 0;
int i = 1;
int prefixLen = 0;
while (i < m) {
if (pattern.charAt(prefixLen) == pattern.charAt(i)) {
prefixLen++;
next[i++] = prefixLen;
} else {
if (prefixLen == 0) {
next[i++] = 0;
} else {
prefixLen = next[prefixLen - 1];
}
}
}
return next;
}
public static int kmpSearch(String text, String pattern) {
int[] next = buildNext(pattern);
int n = text.length();
int m = pattern.length();
int i = 0, j = 0;
while (i < n) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
} else if (j > 0) {
j = next[j - 1];
} else {
i++;
}
if (j == m) return i - j;
}
return -1;
}
public static void main(String[] args) {
String text = "ABABDABACDABABDABAB";
String pattern = "ABABCABAB";
int result = kmpSearch(text, pattern);
if (result != -1) {
System.out.println("Pattern found at index: " + result);
} else {
System.out.println("Pattern not found");
}
}
}
|
微信
