一、定义
本文主要介绍子字符串查找的各类常用算法，如朴素匹配算法（暴力查找）、KMP算法、BM算法等。各类匹配算法的比较见下图：
1-1 各类字符串匹配算法比较
可以看到，对于子字符串查找，最佳性能基本是和文本长度N成正比：
- 暴力查找算法实现简单，且在一般情况下都能工作良好，但是具体与文本规律有关，不能保证性能。
- KMP算法能够保证线性级别的性能，且文本指针不需要回退，需要额外的内存空间。
- BM算法一般都是亚线性级别，其性能通常要比KMP算法好，需要额外的内存空间。
- RK算法基于散列值的计算，一般不需要回退文本指针，但是存在冲突的可能，其性能也是线性级别。
二、暴力查找算法
2.1 定义
暴力查找算法（brute force，也称为朴素匹配算法），其思路就是，用指针i标识正在匹配的文本字符，指针j标识正在匹配的模式字符串：
- 如果当前字符匹配成功（即
txt[i] == ptn[j]），则i++，j++，继续匹配下一个字符； - 如果失配（即
txt[i]! = ptn[j]），则回溯指针i（i = i - j + 1），j = 0，即每次匹配失败时，i回溯，j重置为0。
2-1 暴力查找算法示例
2.2 实现
/**
* 基于回退的暴力查找子字符串
* @param pat 模式字符串
* @param txt 文本
*/
public static int search2(String pat, String txt) {
int m = pat.length();
int n = txt.length();
int i, j; //指针i跟踪文本，指针j跟踪模式字符串
while(i < n && j < m) {
if (txt.charAt(i) == pat.charAt(j)) {
i++;
j++;
}
else {
i = i-j+1;
j = 0;
}
}
if (j == m) return i - j; // found
else return -1; // not found
}
2.3 性能分析
- 时间复杂度：
最坏情况：O(MN)
平均情况：O(M+N)
其中 M:模式字符串长度 , N:文本长度
