2.如果不存在和已匹配后缀完全匹配的子串，则在已匹配后缀中找到最长的真后缀，且是模式串的前缀(t[m-s…m]=P[0…s])


3.如果完全不存在和好后缀匹配的子串，则右移整个模式串。

BM算法在实际匹配时，考虑上面两种策略，当匹配失败发生时，会选择能够移动的最大的距离，来去移动模式串，从而加速匹配。实际情况，失配字符移动策略已经能很好的加速匹配过程，因为模式串本身字符数量是要少于文本串的，Quick Search algorithm（Sunday）正是利用这一策略的算法（有些许不同），或者说是一种简化版的BM算法。

Sunday 算法是 Daniel M.Sunday 于 1990 年提出的字符串模式匹配。其效率在匹配随机的字符串时比其他匹配算法还要更快。Sunday 算法的实现可比 KMP，BM 的实现容易的多。

Sunday算法思想跟BM算法很相似，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在模式串中出现则直接跳过，即移动步长= 模式串长度 1；否则，同BM算法一样其移动步长=模式串中最右端的该字符到末尾的距离 1。

文本串T中字符“c”和模式串中的字符“d”不匹配。我们观察文本串参与匹配的末位的下一个字符“e”，可以知道“e”没有出现在模式串中。于是移动模式串长度 1。


继续匹配，我们发现文本串T中字符“a”和模式串中的字符“d”不匹配。我们观察文本串参与匹配的末位的下一个字符“a”，可以知道“a”出现在模式串中（最右的位置）。于是移动模式串该字符到末尾的距离 1。

Rabin-Karp 算法，由 Richard M. Karp 和 Michael O. Rabin 在 1987 年发表，它也是用来解决多模式串匹配问题的。该算法实现方式与上述的字符匹配不同，首先是计算两个字符串的哈希值，然后通过比较这两个哈希值的大小来判断是否出现匹配。

为了帮助更好的解决字符串匹配问题，哈希函数应该具有以下属性:

1.高效的、可计算的

2.更好的识别字符串

3.在计算hash(y[j 1 ..j m])应该可以容易的从hash(y[j..j m-1])和y[j m]中得到结果，即hash(y[j 1 ..j m])=rehash(y[j],y[j m],hash(y[j..j m-1])

我们定义hash函数如下：

hash(w[0 ..m-1])=(w[0]*2^m-1 w[1]*2^m-2 ··· w[m-1]*2^0) mod q

由于计算的hash值可能会很大，所以需要取模操作，q最好选取一个比较大的数，且是一个质数，w[i]表示y[i]对应的ASCII码。

hash(w[1..m])=rehash(w[0],w[m],hash(w[0..m-1]))

rehash(a,b,h)= ((h-a*2^m-1)*2 b) mod q

匹配过程中，不断滑动窗口来计算文本串的hash值和模式串的是否相同，当出现相同时，还需要再检查一遍字符串是否真正相同，因为会出现哈希碰撞的情况。