匹配_Rabin_karp匹配算法

定义

假设文本是一个长度为n的数组 T[1...n]，而模式是一个长度为m的数组P[1...m]，其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,...z}。
字符数组P和T通常称为字符串。

原理

假设 M={0,1,2,3...,9}，这样每个字符都是十进制数字。我们可以用长度为k的十进制数来表示由k个连续的字符组成的字符串。

给定一个模式P[1...m]，假设p为它对应的十进制数值。给定一个文本T[1...n]，假设t_s表示长度为m的字符串T[s+1,...s+m]所对应的十进制值，其中s=0,1,...,n-m。则当且仅当T[s+1,...s+m]=P[1...m]时有p=t_s。则总能够在O(m)时间内计算出p的值，在O(n-m+1)时间内计算所有t_s的值。则通过比较p和每一个t_s的值，能在O(m)+O(n-m+1)=O(n)时间内计算出所有的有效偏移。

通常假定每个字符都是以d为基数表示的数字，其中d=|M，表示有限字母集合M的大小

可以利用霍纳法则在O(m)时间内计算出p与t_0:

• p=P[m]+10(P[m-1]+10(P[m-2]+...+10(P[2]+10P[1])...))
• t_0=T[m]+10(T[m-1]+10(T[m-2]+...+10(T[2]+10T[1])...))

然后在O(n-m)内计算出t_1、t_2、...t_<n-m>: t_<s+1>=10(t_s-10^(m-1)*T[s+1])+T[s+m+1]

但是有可能p和t_s的值太大，导致不方便对其进行操作。如果P包含m各字符，那么p(m位数)上 每次算术运算需要“常数”时间这一假设就不成立。我们可以选择一个合适的模q来计算p和t_s的模。
我们可以在O(m)时间内计算出模q的p值，然后在O(n-m+1)时间内计算出模q的所有t_s值。
另 h = d^(m-1)(mod q) ，则：
t_<s+1>=(d(t_s-T[s+1]h)+T[s+m+1]) mod q

但是基于模q得出的结果： t_s = p (mod q) 并不能说明 t_s=p。我们对于这样的s称为伪命中点，还需要进一步检测条件 P[1...m]=T[s+1,...s+m] 成立

步骤

• 初始化：计算p和 t_0
• 遍历s从0到n-m(包含n-m)：
  • 找到所有的p=t_s的偏移s，检查若P[1...m]=T[s+1,...s+m]，则将结果s放入结果std::vector中
• 返回结果std::vector

性能

rabin_karp 匹配算法的预处理时间为O(m)，最坏情况下的运行时间为O((n-m+1)m)，在平均情况下他的运行时间还是比较好的

实现