kmp算法的RK串匹配

programRK;begin{计算x,x:=d↑（m-1）modq}x=1fori=1tom-1dox=（32*x)modq{计算模式W的散列函数值}s=0fori=1tomdos=((s*32）+ord(w[i]))modq{计算正文T的第一个长度为m的字符段的散列函数值}t=0fori=1tomdot=(t*32+ord(w[i]))modq{如果正文的第一个长度为m的字符段和模式有相同的散列函数值，则进行匹配检查.否则，以及在匹配检查失败情况下，继续计算下一个字符段的散列函数值}i=1whilei<=n-mdoifs=t{进行匹配检查}k=1j=iwhile(t[j]=w[k])and(k<=m)doj=j+1k=k+1endwhileifi<n-m{计算下一字符段的散列函数值}t=((t-x*ord(t[i]))*32+ord(t[i+m]))modqi=i+1endifendifendwhilereturn“FAILURE”end显然，如果不计执行匹配检查的时间，则RK算法的剩余部分执行时间是Θ（m+n)。不过，如果计及执行匹配检查的时间，则在理论上，RK算法需要时耗Θ（mn）。但是，我们总可设法取q适当大，使得mod函数在计算机中仍可执行而冲突（即不同的字符串具有相同的散列值）又极小可能发生，而使算法的实际执行时间只需Θ（m+n）。
BM算法
BM算法和KMP算法的差别是对模式串的扫描方式自左至右变成自右至左。另一个差别是考虑正文中可能出现的字符在模式中的位置。这样做的好处是当正文中出现模式中没有的字符时就可以将模式大幅度滑过正文。
BM算法的关键是根据给定的模式W[1,m]，，定义一个函数d: x->{1,2，…，m},这里x∈∑。函数d给出了正文中可能出现的字符在模式中的位置。