目录

字符串匹配问题：

简单匹配算法的分析：

7.2 Rabin-Karp算法

基于指纹的算法 ：

 使用Hash函数

预处理：求fingerprint

步骤：关键在每次移位的计算

Rabin-Karp算法：

分析：

应用：

 KMP算法

 自动机搜索

前缀函数：

 前缀表：

预先计算大小为m的前缀表来存储π[q]的值（0<=q

 KMP分析

BMH算法： 

逆简单算法：

启发式方法：

偏移表：

伪代码：

算法实现：

BMH分析：

---

字符串匹配问题：

输入：

文本T = "at the thought of"

n=length(T) =17

模式 P="the"

m=length(P) = 3

输出：移动到s （S是文本里的下标）

s是满足T[s....s+m-1] = P[0..m-1] 的最小整数（0<= s<=n-m）

如果不存在这样的s 返回-1

简单匹配算法： 

暴力搜索：        检查从 0 到n-m的所有值

伪代码

Native-Search (T,P)
for s <- 0 to n-mj <- 0//check if  T[s..s+m-1] = P[0..m-1]while T[s+j]= P[j] doj <- j+1if j = m return s
return -1 

令 T="at the thought of" , P="though"需要多少次比较？

简单匹配算法的分析：

最坏情况：

• 外层循环： n-m 【P的第一个字母和T的字母对齐多少次】
• 内层循环：m 【】
• 总计(n-m)*m = O(nm)
• 何种输入产生最坏情况？【每次P都是匹配到最后一个才发现不匹配】

最好情况：n-m 【每次一开始就发现不匹配】

完全随机的文本和模式：O(n-m)

思路： 如果文本完全随机，字母表大小是k，那么随便两个字母 每个字母是1/k 。P和T的第一个字母比较，他们匹配的概率是1/k ，不匹配的概率是1-1/k 。恰好比较两次的概率是（1/k）*（1-1/k）

7.2 Rabin-Karp算法

指纹想法

假设：

• 我们可以在O(m)时间内计算一个P的指纹f(P)
• 如果指纹不相等 f(P) ≠ f( T[s..s+m-1] )，那么子串不相等 P ≠  T[s..s+m-1] 
• 我们可以在O(1)时间比较指纹
• 我们可以在O(1)时间 从 f( T[s..s+m-1] ) 计算 f ' ( T[s+1..s+m] )  当前指纹和挪一位之后的指纹

基于指纹的算法 ：

令字母表为∑ = { 0,1,2,3,4,5,6,7,8,9 }

令指纹为一个十进制数，即 f("1045") =1*10**3 + 0*10**2 +4*10**1 + 5 =1045

Fingerprint-Search (T,P)fp <- compute f(P)  //模式 或者说基准子串f <- compute f(T[0..m-1])for s <- 0 to n-m doif fp = f return sf <- (f - T[s]*10**(m-1) )*10 + T[s+m]return -1

运行时间是 2 O(m) + O( n-m) = O(n) 

开始算两个指纹 2 O(m) + 依次比较的时间 n-m轮 每轮是O(1) 

 使用Hash函数

问题： 实际上我们并不能假设我们可以对m位数在O(1)时间内进行算术运算。

解决方案：使用hash函数 h = f mod q 

例如，如果q=7 , h("52 ") = 52 mod 7 =3 

h(S1) ≠ h(S2) => S1 ≠ S2

但是h(S1) = h(S2) 不意味着 S1 = S2 

例如 ，如果q=7 ,h("73")=3 但 “73”≠“52”

但mod算数运算——操作数限定在q以内，如果q足够小/常数，就可以在O(1)

时间内 进行算术运算

(a+b)mod q= (a mod q +b mod q)mod q

(a*b)mod q=(a mod q)*(b mod q)mod q 

预处理：求fingerprint

拆开(秦九韶) 

fp=P[m-1] + 10* ( P[m-2] + 10*(P[m-3] +...+10*(P[1] + 10* (P[0]) ) )   mod q

同样可以从 T[0...m-1]计算ft

例如 P="2531" , q=7 ,fp =?

步骤：关键在每次移位的计算

ft =  ( ft-T[s]*10**(m-1) mod q) *10 + T[s+m] ) mod q

// T[s+m] 小于q 不需要mod q 。式子T[s]*10**(m-1)可能大于q 需要mod q ,而T[s]也是小于q ，所以10**(m-1)需要mod q

10**(m-1) mod q在预处理中计算一次

Rabin-Karp算法：

Karbin-Karp-Search (T,P)q <- a prime larger than m//选择一个大于m的素数q ,用来 c <- 10**(m-1) mod q //run a loop multiplying by 10 mod qfp <- 0 ; ft <- 0for i <- 0 to m-1 //preprocessingfp <- (10*dp +P[i] ) mod qft <- (10*ft +T[i] ) mod qfor s <- 0 to n-m //matching匹配if fp= ft then //指纹相等不代表字符串匹配if P[0..m-1] = T[s..s+m-1] return s//还需要匹配每一位字符ft <- (  (ft - T[s]*c ) *10 + T[s+m ] ) mod q //移位 return -1  

比较多少次？

分析：

如果q是素数，hash函数会使m位字符串在q个值中均匀分布。

        因此，仅有s个轮换中的每q次才需要匹配指纹（匹配慢，需要比较O(m)次 ）。每q次需要一次指纹，其他需要一次比较。

期望运行时间（如果q>m）

        预处理：O(m) //需要对每个Pattern字符算一次

        外循环：O(n-m) //从头比到尾

        所有内循环：(n-m)/q * m = O(n-m) //具体指纹比较

        总时间：O(n-m) //线性

最坏运行时间：O(nm)  //和暴力搜索，每次都匹配上，但每次匹配到最后一个字母发现不一样

应用：

 KMP算法

N次比较的匹配

目标：文本中的每个字符仅匹配一次

简单算法的问题：

        没有利用已有部分匹配中的知识

        T="Tweedledee and Tweedledum"  P="Tweedledum"

        T="pappar"  P="pappappappar"

 自动机搜索

算法：

预处理：

        对于每个q (1 <= q <= m-1 ) 和每个α ∈ ∑ 预先计算一个q的新值，记为σ(q,α)

 填一个大小为 m* |∑| 的表

扫描文本：

当不匹配发现时，（P[q] ≠ T[s+q] ）：置 s=s+q - σ(q,α)+ 1 ,且 q= σ(q,α)

 分析：

匹配阶段 O(n)

缺点：内存过多，O（m|∑ | ），过多的预处理 O（m|∑ | ）

前缀函数：

 前缀表：

预先计算大小为m的前缀表来存储π[q]的值（0<=q<m  , m= length(P)）

 

KMP-Search(T,P)
{π<- Compute-Prefix-Table(P)q <- 0 //匹配字符的数目 for i <- 0 to n-1 //从左到右扫描文本 while q >0 and P[q] ≠T[i] doq <- π[q] if P[q] = T[i] then q <- q+1 if q= m then return i-m+1return -1
} 
//Compute-Prefix-Table 是P上执行KMP算法的本质 

 KMP分析

 最坏情况运行时间：O(n+m)

•  主算法：O(n)
• Compute-Prefix-Table : O(m)

空间：O( m ) 

主算法：最多匹配两次

BMH算法： 

逆简单算法：

从P的后面开始搜索。

Boyer and Moore

Reverse-Naive-Search (T,P)for s <- 0 to n-mj <- m-1 //从结尾开始//check if T[s..s+m-1] = P[0..m-1]while T[s+j] = P[j] doj <- j-1if j< 0 return sreturn -1 

运行时间和简单算法相同。

启发式方法：

 匹配P和T，从后往前匹配，

et a和e发现了不匹配，这个时候，只看最后字母e ,能和P里面的哪一个匹配（除了最后一个e 这位比较过了），

没有 ，这时候可以把P串到e的后面，相当于吧“date”串到cative这个地方，

再从后往前比，e和v不一样，把T[s+n-1]就是这个v 匹配到模式当中，去掉最后一位，比较过的这位以外，最右出现。我们知道前面没有v , 就可以把date再往后串4位 ，

这时候就把d对齐到v后边这个e的位置，然后，发现e和a不匹配，

再到P的前缀中找a , 发现有一个a ,就把这两个a 的位置对齐，然后e t a d 就找到了。

偏移表：

如果最后这个字母出现在P的前缀中，算P往后移动多少位才能跟他对齐，如果不出现，就跳过。

在预处理中，计算大小为|∑| 的偏移表。

 例：P="kettle " 去掉最后一个字母的前缀 "kettl" 如果最后一个字母是"e" shift[e] = 4 ,shift[l]=1,shift[t]=2,shift[k]=5 

伪代码：

BMH-Search (T,P)n <- the length of Tm <- the length of P|∑| <- the length of OffsetTable//计算P的偏移表 for c <- 0 to |∑| -1 shift[c] =m //默认值for k <- 0 to m-2shift[P[k]] = m-1 -k //查searchs <- 0while s <= n - m do j <- m-1 //从结尾开始// check if T[s..s+m-1] = P[0..m-1]while T[s+j] = P[j] doj <- j-1 if j < 0 return ss <- s + shift[ T[s+m-1] ] //shift by last letterreturn -1 

算法实现：

#include<bits/stdc++.h>
using namespace std;const int maxnum=1005;
int shift[maxnum];int BMH(string &T,string &P)
{int n=T.length();int m=P.length();//偏移表for(int i=0;i<maxnum;i++){shift[i]=m;//默认值 }//模式串P中每个字母出现的最后下标，（除最后一个字母）//主串从 不匹配最后一个字符，需要左移的位数 for(int i=0;i<=m-2;i++){shift[P[i]]=m-1-i;//字符-数值 }int s=0;// 模式串开始位置在主串的哪里while(s <= n-m){int j=m-1;// 从模式串尾部开始匹配while(T[s+j]==P[j]){j=j-1;if(j<0)return s;// 匹配成功} // 找到坏字符(当前跟模式串匹配的最后一个字符)// 在模式串中出现最后的位置(最后一位除外)// 所需要从模式串末尾移动到该位置的步数s=s+shift[ T[s+m-1] ];}return -1;
}int main()
{string T,P;while(true){getline (cin,T);getline(cin,P);//int res=BMH(T,P);if(res==-1 )cout<<"不匹配"<<endl;else cout<<"模式串P在主串的位置为："<<res<<endl;}return 0;
} 

测试

at the thought of
though
模式串P在主串的位置为：7
aaaaaaab
aaa
模式串P在主串的位置为：0

BMH分析：

 最坏情况运行时间：

•         预处理：O( |∑| +m )
•         搜索：O(nm) ---
•         总计：O(nm)

空间：O( |∑|  )

•         和m独立

在真实数据集合上很快。