子字符串查找算法：
- 暴力子字符串查找算法
- KMP 算法
- RM 算法
术语：
- 文本：完整的字符串
- 模式字符串：需要在文本中查找的子串
暴力子字符串查找算法
性能：
- 在极端情况下（存在很多重复的字符），时间复杂度是 O(MN)
- 一般情况下（不需要完整地比对模式串），时间复杂度是 O(M + N)
思路：枚举出文本中的所有和模式串长度相等的子串进行对比
算法实现1：
public class BruteForce1 {
public static int search(String txt, String pattern) {
int n = txt.length();
int m = pattern.length();
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (pattern.charAt(j) != txt.charAt(j + i)) {
break;
}
}
if (j == m) {
return i;
}
}
return -1;
}
}
测试：
class BruteForce1Test {
@Test
void search() {
Assertions.assertEquals(0, BruteForce1.search("Hello World", "Hello"));
Assertions.assertEquals(6, BruteForce1.search("Hello World", "World"));
Assertions.assertEquals(-1, BruteForce1.search("Hello World", "Hi"));
}
}
思路：枚举文本的每个和模式串长度相同的子串，对比失败时回退指针 i, j
算法实现2：
public class BruteForce2 {
public static int search(String txt, String pattern) {
int n = txt.length();
int m = pattern.length();
int i, j;
for (i = 0, j = 0; i < n && j < m; i++) {
if (pattern.charAt(j) == txt.charAt(i)) {
j++;
} else {
i -= j;
j = 0;
}
}
if (j == m) {
return i - m;
}
return -1;
}
}
测试：
class BruteForce2Test {
@Test
void search() {
Assertions.assertEquals(0, BruteForce2.search("Hello World", "Hello"));
Assertions.assertEquals(6, BruteForce2.search("Hello World", "World"));
Assertions.assertEquals(-1, BruteForce2.search("Hello World", "Hi"));
}
}
KMP 算法
本节重点：
- DFA 如何使用
- DFA 如何构造
全称：Knuth-Morris-Pratt 子字符串查找算法（三位发明者的名字）
基本思想：利用已经比较过的字符信息，实现在匹配失败时，总是将 j 设置为某个值使 i 不回退
可能性：当匹配失败时，可以将模式串向右移动来避免指针 i 回退
文本串：AABAABAAAB
模式串：AABAAA
-> AABAAA
实现：对模式串进行预处理，构造 DFA（确定有限状态自动机），在遍历文本串的字符时，可以从 DFA 得到下一个 j 的值，即状态
DFA: dfa[txt.chatAt(i)][j] 的值是和文本串的下一个字符 txt.chatAt(i+1) 比较的 j 值
算法实现：
public class KMP {
private static final int R = 256; // 字符集大小
private String pattern;
private int m;
private int[][] dfa;
/**
* 根据模式串构造确定有限状态自动机 DFA
* */
public KMP(String pattern) {
this.pattern = pattern;
this.m = pattern.length();
dfa = new int[R][m];
// 初始化第一列
dfa[pattern.charAt(0)][0] = 1;
// 初始化其他的列，从第二列开始
// 当 txt[i..i+j] 匹配失败时，从 txt[i+1] 开始匹配，
// 这里可以想象成DFA正在处理第 2 个字符的匹配情况
// X 记录重启状态
for (int j = 1, X = 0; j < m; j++) {
for (int c = 0; c < R; c++) {
dfa[c][j] = dfa[X][j]; // 匹配失败，将 dfa[][X] 复制到 dfa[][j]
}
dfa[pattern.charAt(j)][j] = j + 1; // 匹配成功，将 dfa[pattern.charAt(j)][j] 设置成 j + 1
X = dfa[pattern.charAt(j)][X]; // 更新 X，即从 txt[i+1] 开始匹配或者说在构建自动的同时也在使用自动机
}
}
/**
* 在文本串中查找子串
* 将文本串的字符逐个放到 DFA 中，直到 DFA 达到终止状态或文本串结束
* */
public int search(String txt) {
int n = txt.length();
int i, j;
for (i = 0, j = 0; i < n && j < m; i++) {
j = dfa[txt.charAt(i)][j];
}
if (j == m) {
return i - m;
}
return -1;
}
}
测试：
class KMPTest {
@Test
void search() {
KMP kmp = new KMP("Hello");
Assertions.assertEquals(0, kmp.search("Hello World"));
Assertions.assertEquals(4, kmp.search("Say Hello"));
Assertions.assertEquals(-1, kmp.search("hello world"));
}
}
应用场景：
- 文本串和模式串的重复性很高
- 文本串是长度不确定的输入流