5.3 子字符串查找
字符串的一种基本操作就是子字符串的查找：给定一段长度为N的文本和一个长度为M的模式（pattern）字符串，在文本中找到一个和该模式相符的子字符串。解决该问题的大部分算法都可以容易的扩展成为找出文本中所有和该字符串相符的子字符串、统计该模式在文本中出现的次数、或者找出上下文（和该模式相符的子字符串周围的文字）的算法。
5.3.1历史简介
略
5.3.2 暴力子字符串查找算法
子字符串查找的一个显而易见的方法就是在文本模式可能出现匹配的任何地方检查匹配是否存在。这段程序使用了一个指针i跟踪文本，一个指针j跟踪模式。对于每个i，代码首先将j重置为0并不断增大，直至找到了一个不匹配的字符或是模式结束（j==M）为止。
如果在模式字符串结束前文本字符串就结束了（i==N-M+1），那么就没找到匹配：模式字符串在文本中不存在。我们约定在不匹配时返回N的值。
代码：
/**
* 暴力子字符串查找算法
* @param pat 模式
* @param txt 文本
* @return 匹配到的第一个位置,否则返回txt 的长度N
*/
public static int search(String pat,String txt){
int M=pat.length();
int N=txt.length();
for (int i = 0; i <=N-M ; i++) {
int j;
for (j = 0; j < M; j++) {
if(pat.charAt(j)!=txt.charAt(i+j))
break;
}
if(j==M) return i; //找到匹配
}
return N; //未找到匹配
}
下面给出暴力子字符串查找算法的另一种实现，这两种实现都是一样的。
5.3.3 Knuth-Morris-Pratt子字符串查找算法
KMP算法发明的的基本思想是当出现不匹配的时候，就能知晓一部分文本的内容。
注意：算法第四版的KMP算法试求一个dfa数组，而国内其他教材是求一个next数组，我认为没有孰优孰劣之分，能掌握一种即掌握KMP算法。
假设字母表中只有两个字符，查找的模式字符串为BAAAAAAAAA。现在假设已经匹配了模式的5个字符，第6个字符匹配失败。当发现不匹配的字符时，可以知道文本的前6个字符肯定是BAAAAB（前5个匹配，第六个失败）文本指针指向的是末尾的字符B。你可以观察到，这里不需要退回文本指针i，因为正文的前4个字符都是A，均与模式的第一个字符不匹配。另外，i当前指向的字符B和模式的第一个字符相匹配，所以可以直接将i加1，比较文本的下一个字符和模式的第二个字符。这说明，可以将暴力子字符串查找算法中实现的else语句替换为j=1（且不将i+1）。
5.3.3.1 模式指针的回退
在KMP子字符串的查找算法中，不会回退文本指针i，而是使用一个数组dfa[] []来记录匹配失败时模式指针j应该回退多远。对于每个字符c，在比较了c和pat.charAt(j)之后，dfa[c] [j]表示的是应该和下个文本字符比较的模式字符的位置。
5.3.3.2 KMP算法
只要计算出了dfa[] []数组，就得到了后面框柱所示的子字符串查找算法。
注：关于KMP算法 ，实在是晦涩。。。 读者也是一知半解仅仅可以应用的水平
推荐下面几篇文章，阅读，结合代码，亲自模拟一下dfa的构造过程和算法的执行。我相信你应该也可以理解
算法 KMP字符串查找算法
public class KMP {
private String pat;
private int[][] dfa;
public KMP(String pat) {
this.pat = pat;
int M = pat.length();
int R = 256;
dfa = new int[R][M];
dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < M; j++) {
//计算dfa
for (int c = 0; c < R; c++) {
dfa[c][j] = dfa[c][X]; //匹配失败情况下的值
}
dfa[pat.charAt(j)][j] = j + 1; //匹配成功情况的值
X = dfa[pat.charAt(j)][X]; //更新重启状态
}
}
public int search(String txt) {
//在txt上模拟DFA运行
int i, j, N = txt.length(), M = pat.length();
for (i = 0, j = 0; i < N && j < M; i++) {
j = dfa[txt.charAt(i)][j];
}
if (j == M) return i - M; //找到匹配(到达模式字符串的结尾)
else return N; //未找到匹配(到达文本字符串的结尾)
}
}
在实际应用中，它比暴力算法的速度优势并不明显，因为极少有应用程序需要在重复度很高的文本中查找重复性很高的模式。但该方法的一个优点就是不需要在输入中回退。这让KMP更适合在长度不确定的输入流（例如标准输入）中查找，需要回退的算法在这种情况下需要复杂的缓冲机制。
5.3.4 Boyer-Moore字符串查找算法
当可以在文本中回退时，如果可以从右向左扫描模式字符串并将它和文本匹配，那么就能得到一种非常快的字符串查找算法。例如，查找子字符串BAABBAA时，如果匹配了第七个和第六个字符，但在第5个字符处匹配失败，那么马上可以向右移动7个位置并继续检查文本的第14个字符。这是因为部分匹配找到了XAA而X不是B，而这三个连续的字符在模式中是唯一的。
5.3.4.1 启发式的处理不匹配的字符
看图，它显示了在文本FINDINAHAYSTACKNEEDLE中查找模式NEEDLE的过程。因为是从右向左与模式进行匹配，所以会首先比较模式字符串中的E和文本中的N（位置为5的字符）。因为N也在模式字符串中，所以将模式字符串向右移动5个位置，将文本中的字符N和模式字符串中（最左侧）的N对齐。然后比较模式字符串最右侧的E和文本中的S（位置在第10个字符），匹配失败。但因为S不包含在模式字符串中,所以可以将模式字符串向右移动6个位置.此时模式字符串最右侧的E和文本中位置为16的E匹配，但文本下一个（位置为15的）字符为N，匹配再次失败。于是和第一次一样，将模式字符串向右移动4个位置。最后从20开始从右向左扫描，发现文本中含有与模式匹配的子字符串。
5.3.4.2 起点
要实现启发式的处理不匹配的字符，我们使用数组right[]记录字母表中的每个字符在模式中出现的最靠右的地方（如果字符在模式中不存在则表示为-1.）这个值揭示了如果字符出现在文本中且查找时匹配失败，应该向右跳多远。要将right[]初始化，首先应该设置所有元素为-1，然后对于0到M-1的j，将right[pat.charAt(j)]设为j。
5.3.4.3子字符串的查找
计算完right[]之后，我们用一个索引i在文本中从左向右移动，用另一个索引j在模式中从右向左移动。
内循环会检查正文和模式字符串在位置i是否一致。如果从M-1到0的所有j，txt.charAt(i+j)都和pat.charAt(j)相等，就找到了一个匹配。
否则匹配失败，则会遇到下面三种情况
- 如果造成匹配失败的字符不包含在模式字符串中，将模式字符串向右移动j+1个位置（即将i增加j+1）
- 如果造成匹配失败的字符包含在模式字符串中，可以使用right[]数组来将模式字符串和文本对齐，使得该字符和它在模式字符串中出现的最右位置匹配。
- 如果这种方法无法增大i，至少将i加1保证字符串向右移动了一个位置。
代码：
public class BoyerMoore {
private int[] right;
private String pat;
public BoyerMoore(String pat) {
this.pat = pat;
int R = 256;
int M = pat.length();
right = new int[R];
for (int c = 0; c < R; c++) {
right[c] = -1; //不包含在模式字符串中的字符值为1
}
for (int j = 0; j < M; j++) {
right[pat.charAt(j)] = j; //包含在模式字符串的字符的值为它在其中出现的最右位置
}
}
public int search(String txt) {
int N = txt.length();
int M = pat.length();
int skip;
for (int i = 0; i <= N - M; i++) {
skip = 0;
for (int j = M - 1; j >= 0; j--) {
if (txt.charAt(i + j) != pat.charAt(j)) {
skip = j - right[txt.charAt(i + j)];
if (skip < 1) skip = 1;
System.out.println(skip);
break;
}
}
if (skip == 0) return i; //找到匹配
}
return N; //未找到匹配
}
}
5.3.5 Rabin-Karp指纹字符串查找算法
我们需要计算字符串的散列函数，然后用相同的散列函数计算文本中所有可能的M个字符的子字符串散列值并寻找匹配。如果找到了一个散列值和模式字符串相同的子字符串，那么继续验证两者是否相等。
5.3.5.1 基本思想
长度为M的字符串对应着一个R进制的M位数。为了用一张大小为Q的散列表来保存这种类型的键，需要一个能够将R进制的M位数转换为一个0到Q-1之间的int值散列函数。除留余数法是一个好的选择。在实际应用中会选择一个随机的素数Q，在不溢出的情况下选择一个尽可能大的值。理解这个方法最简单的办法就是取一个较小的Q和R=10的情况。
5.3.5.2 计算散列函数
private long hash(String pat,int M){
long h=0;
for (int i = 0; i < M; i++) {
h=(h*R+pat.charAt(i))%Q;
}
return h;
}
5.3.5.3 关键思想
5.3.5.4 实现
构造函数为模式字符串计算了散列值pathHash并在变量RM中保存了R的m-1次方 mod Q的值。
hashSearch()方法开头计算了文本的前M个字母的散列值并将它和模式字符串的散列值进行比较，如果不匹配，那么它会在文本中继续前进。
public class RabinKarp {
private String pat; //模式字符串(仅拉斯维加斯算法需要)
private long pathHash; //模式字符串的散列值
private int M; //模式字符串的长度
private long Q; //一个很大的素数
private int R=256; //字母表的大小
private long RM; //R^(M-1)%Q
public RabinKarp(String pat) {
this.pat = pat;
this.M=pat.length();
Q=997;
RM=1;
for (int i = 1; i <=M-1 ; i++) {
RM=(RM*R)%Q;
}
pathHash=hash(pat,M);
}
private long hash(String pat,int M){
long h=0;
for (int i = 0; i < M; i++) {
h=(h*R+pat.charAt(i))%Q;
}
return h;
}
public boolean check(int i){ //蒙特卡洛算法
return true; //对于拉斯维加斯算法,检查模式与txt(i...i-M+1) 的匹配
}
private int search(String txt){
int N=txt.length();
long txtHash=hash(txt,M);
if(pathHash==txtHash&&check(0)) return 0; //一开始就匹配成功
for (int i = M; i < N; i++) {
//减去第一个数字,加上最后一个数字,再次检查匹配
txtHash=(txtHash+Q-RM*txt.charAt(i-M)%Q)%Q;
txtHash=(txtHash*R)+txt.charAt(i);
if(pathHash==txtHash&&check(i-M+1)) return i-M+1; //找到匹配
}
return N; //未找到匹配
}
}
5.3.6 总结
