子字符串查找在计算机中有非常广泛的应用，比如在网页中找到你感兴趣的单词或句子，有关子字符串查找的方法也有很多，一般本科阶段都会教授的算法就是KMP算法，所以本文暂时不对KMP算法进行介绍，而是介绍另外的两种算法——Boyer-Moore算法和Rabin-Karp算法。
Boyer-Moore算法
我们假定需要被搜索的字符串是HERE IS A SIMPLE EXAMPLE，而你需要搜索的信息是EXAMPLE。那么，我们的查找开始。
从头开始比较两个字符串，从尾部开始比较，此时S和E不匹配，则我们可以直接判断EXAMPLE这个字符串整体上不匹配，我们称不匹配的字符S为坏字符，同时S也不在EXAMPLE中，所以我们直接把EXAMPLE后移到S的下一个位置继续匹配。
由此我们可以看出P和E不匹配，P成了坏字符，同时P也存在于EXAMPLE中，所以我们不能直接把EXAMPLE直接移动到P之后，而是移动到两个P对齐，也就是把EXAMPLE右移2位。之所以要这样做，是因为这个算法首先以末尾字符进行比较，如果不匹配可能是因为开头出了问题。那么如何知道遇到坏字符时，搜索词如何移动呢？有一个简单的公式：
这里的坏字符的位置是相对EXAMPLE来说的，比如在上面的例子中，P和E不匹配的位置是EXAMPLE的第6位(从0起计数)，所以坏字符的位置是6，而在EXAMPLE中上一次P出现的位置是4(从0起计数)，由公式可得移动距离是2。如果坏字符没有出现在搜索词(EXAMPLE)中，则出现位置置为-1。
经过从尾部开始的几次比较后，我们发现后缀的MPLE都能匹配成功，所以我们把其称为好后缀，其中MPLE、PLE、LE、E都是好后缀。
此时的I和A不匹配，触发了坏字符规则，根据计算位2-(-1)=3，则代表EXAMPLE右移3位。但是还有没有更有效率的移动呢。答案是有的。我们此时使用好后缀来解决问题，同样也有一个简单的公式：
这里所指的好后缀的位置是指后缀中最后一个字符所在的位置，比如ABCDEFAB中，AB是好后缀的话，那么位置是7(从0起计数，以B为标准)，而上一次出现的位置是1(从0起计数，以B为标准)。所以后移6位，我们就能把第一个AB移动到和第二个AB重合。如果好后缀未出现在搜索串当中，则位置置为-1。则此时出现了需要注意的问题，那就是如果好后缀有多个的情况下如何处理？例如BABCDAB中我们假定DAB、AB、B都是好后缀，那么该匹配哪个的上一次出现位置。答案是B的，因为这个规则要求，除了最长的那个好后缀外，其余好后缀上一次出现的位置必须在头部。
了解了以上规则后，我们继续匹配。
此时根据坏字符规则本来只应该移动2-(-1)=3位，但是据上图来看其实移动了6位，我们此时就知道它移动的规则是根据好后缀进行的。由此我们可知，其移动距离的选择是坏字符和好后缀之间的较大值。
至此匹配结束。
代码：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
34public class BoyerMoore {
private int[] right;
private String pat;
BoyerMoore(String pat){
this.pat = pat;
int M = pat.length();
int R = 256;
right = new int[R];
for(int c=0;c<R;c++)
right[c]=-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){
skip = 0;
for(int j=M-1;j>=0;j--){
if(pat.charAt(j)!=txt.charAt(i+j)){
skip = j-right[txt.charAt(i+j)];
if(skip<1)
skip=1;
break;
}
}
if(skip==0)
return i;
}
return N;
}
}
分析：
从上面的代码中我们可以看出，它并没有实现好后缀的部分，而是使用了坏字符的方法进行匹配。
在初始化的过程中，首先构造了一个ASCII码极限的大数组用于存放数据，其中使用了两个for循环，第一个for循环将right数组中的所有值都置为-1。第二个for循环是为了标注出pat字符串中的各位的值，表示每个字符出现的最后位置。
我们还是以待搜索文本为“HERE IS A SIMPLE EXAMPLE”和搜索文本为”EXAMPLE“进行说明。
在初始化过程中，我们对“EXAMPLE“进行right数组的操作。
此时我们进入search方法进行推演。这个方法里面的skip就是用来决定搜索文本的移动距离，进入第二层for循环时，比较就开始了，1
if(pat.charAt(j)!=txt.charAt(i+j))
通过之前的图示我们知道，这一步就是在比较S和E是否相同，结果自然是否定的。既然是否定的，我们就进入了skip的计算，我们知道此时right[txt.charAt(i+j)]为right[S]，而S之前不存在right数组中，所以为-1，结果计算出来就是skip=6-(-1)=7，代表EXAMPLE需要移动7位，和最开始的图推演方式一致。后续的推演过程结合图片的表述应该都能理解。
Rabin-Karp算法
Rabin-Karp算法是一种哈希算法，简单来说就是对搜索文本进行哈希运算，得出一个值，再在带搜索文本中计算同等长度字符串的哈希值进行匹配，若匹配成功则表明找到答案。
那么要进行这个哈希运算最重要的一点就是确定哈希函数，我们首先要理解一个计算方法，那就是如何保证能高效的计算固定长度的哈希值。对于起始于位置i的含有M个字符的子字符串对应的数为：
如果我们右移一位的话就会发现：
这两个式子表明了取余操作的一个基本性质，那就是如果在每次算术操作之后都将结果除以Q并取余，这等价于在完成了所有计算操作之后再将最后的结果除以Q并取余。
我们以26535作为搜索文本，以3141592653589793作为待搜索文本，并且选用997作为散列表的大小。
我们就得到了26535这个字符串的哈希为613。
从上图的计算过程中，我们可以清晰的看到计算的步骤。
代码：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
46public class RabinKarp {
private long patHash; //模式字符串的散列值
private int M; //模式字符串的长度
private long Q; //很大的素数
private int R = 256; //字母表大小
private long RM; //R^(M-1)%Q
public RabinKarp(String pat){
this.M = pat.length();
Q = longRandomPrime();
RM = 1;
for (int i=1;i<M-1;i++)
RM = (R*RM)%Q;
patHash = hash(pat,M);
}
public boolean check(int i){
return true;
}
private long hash(String key,int M){
long h=0;
for(int j=0;j<M;j++)
h = (R*h+key.charAt(j))%Q;
return h;
}
private static long longRandomPrime() {
BigInteger prime = BigInteger.probablePrime(31, new Random());
return prime.longValue();
}
private int search(String txt){
int N = txt.length();
long txtHash = hash(txt,M);
if(patHash==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))%Q;
if(patHash==txtHash)
return i-M+1;
}
return N;
}
}
上述代码比较清晰，主要部分还是在search方法中有关哈希值的计算，这点个人认为无须多说，看到公式之后就能理解原理了。