KMP算法与一个经典概率问题

Readln(str_s); Write(‘t = ’); Readln(str_t); int_i := index( str_s, str_t ); if int_i <> 0 then begin Writeln( 'Found' , str_t,' in ', str_s, 'at ', int_i,' .' ); end else

Writeln( 'Cannot find ', str_t,' in' , str_s, '. '); END. index函数用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到则返回0 编辑本段基本思想

假设在模式匹配的进程中，执行T[i]和W[j]的匹配检查。若T[i]=W[j]，则继续检查T[i+1]和W[j+1]是否匹配。若T[i]<>W[j]，则分成两种情况：若j=1，则模式串右移一位，检查T[i+1]和W[1]是否匹配；若1<j<=m，则模式串右移j-next(j)位，检查T[i]和W[next(j)]是否匹配。重复此过程直到j=m或i=n结束。 文献中，朱洪对KMP算法作了修改，他修改了KMP算法中的next函数，即求next函数时不但要求W[1,next(j)-1]=W[j-(next(j)-1),j-1]，而且要求W[next(j)]<>W[j]，他记修改后的next函数为newnext。显然在模式串字符重复高的情况下,朱洪的KMP算法比KMP算法更加有效。 以下给出朱洪的改进KMP算法和next函数和newnext函数的计算算法。 算法1.1：KMP串匹配算法 输入: 正文串j和模式串W[1,m] 输出: 匹配结果match[1,n] procedure KMP begin

i=1 j=1 while i<=n do while j<>0 and W[j]<>T[i] do j=newnext[j] endwhile if j=m return “success” else j++ i++ endif endwhile return

“failure” end 算法1.2: next函数和newnext函数的计算算法 输入: 模式串W[1,m] 输出: next[1,m+1]和newnext[1,m] function NEXT begin next[1]=newnext[1]=0 j=2 while j<=m do i=next[j-1] while i<>0 and W[i]<>W[j-1]) do i=next[i] endwhile next[j]=i+1 j=j+1 endwhile end function NEWNEXT begin newnext(1)=0 j=2 while j<=m do i=next(j) if i=0 or W[j]<>W[i+1] newnext[j]=i else

newnext[j]=newnext[i] endif j++ endwhile end 朱洪证明了算法1的时间复杂度为O(n)，算法2的时间复杂度为O(m)。 下面是更加简洁的算法： void GetNext(char T[ ],int next[ ]) { next[1]=0; j=1;k=0; while(j<T[0]) if ((k==0)||(T[j]==T[k]) { j++; k++; next[j]=k; } else k=next[k]; } 编辑本段BM算法

BM算法和KMP算法的差别是对模式串的扫描方式自左至右变成自右至左。另一个差别是考虑正文中可能出现的字符在模式中的位置。这样做的好处是当正文中出现模式中没有的字符时就可以将模式大幅度滑过正文。 BM算法的关键是根据给定的模式W[1,m],，定义一个函数d: x->{1,2,…,m} ,这里x∈∑。函数d给出了正文中可能出现的字符在模式中的位置。 函数d的定义如下：对每个x∈∑ 编辑本段基本思想

假设在执行正文中自位置i起“返前”的一段与模式的自右至左的匹配检查中，一旦发现不匹配(不管在什么位置)，则去执行由Wm与ti+d(x)起始的自右至左的匹配检查，这里x是字符t。。它的效果相当于把模式向右滑过d(ti)一段距离。显然,若ti不在模式中出现或仅仅在模式末端出现，则模式向右滑过的最大的一段距离m。图1.1示出了执行BM算法时的各种情况。实线连接发现不匹配以后要进行比较的正文和模式中的字母，虚线连接BM算法在模式向右滑后正文和模式中应对齐的字母，星号表示正文中的一个字母。 图1.1：执行BM算法时的各种情况 BM算法由算法1.3给出，函数d的算法由算法1.4给出。计算函数d的时耗显然是Θ(m)。BM算法的最坏情况时耗是Θ(mn)。但由于在实用中这种情况极少出现，因此BM

算法仍广泛使用。 算法1.3：BM串匹配算法 输入: 正文串W[1,m]和模式串T[1,n] 输出: 匹配结果match[1,n] procedure BM begin i=m Repeat j=m k=i while(j>0)and(w[j]=t[k]) do j=j-1 k=k-1 endwhile i=i+d[t[i]] Until (j=0)or(i>n) If j=0 return “SUCCESS” else return

“FAILURE” endif end 算法1.4: d函数计算法: function d:integer; begin for x∈∑ do d(x)=m for j=m-1 downto 1 do if d(w[j])=m d(w[j]):=m-j endfor end

xi+1=ord(ti+1)dm-1+ord(ti+2)dm-2+…+ord(ti+m) =(xi-ord(ti)dm-1).d+ord(ti+m) 因此有

h(xi+1)=((h(xi)-x·ord(ti))·d+ord(ti+m)mod q ，i=1,2,……,n-m 这里x是一常数，x=dm-1mod q。 这就是计算每一长度为m的字符段的散列函数值的递推公式。RK串匹配算法由算法1.5给出。 算法1.5：RK串匹配算法 program RK; begin {计算x,x:=d↑(m-1) mod q} x=1 for i=1 to m-1 do x=(32*x)mod q {计算模式W的散列函数值} s=0 for i=1 to m do s=((s*32)+ord(w[i])) mod q {计算正文T的第一个长度为m的字符段的散列函数值}

t=0 for i=1 to m do t=(t*32+ord(w[i])) mod q {如果正文的第一个长度为m的字符段和模式有相同的散列函数值,则进行匹配检查.否则,以及在匹配检查失败情况下,继续计算下一个字符段的散列函数值} i=1 while i<=n-m do if s=t {进行匹配检查} k=1 j=i while (t[j]=w[k]) and (k<=m) do j=j+1 k=k+1 endwhile if i<n-m {计算下一字符段的散列函数值} t=((t-x*ord(t[i]))*32+ord(t[i+m])) mod q i=i+1 endif endif endwhile return “FAILURE” end 显然,如果不计执行匹配检查的时间，则RK算法的剩余部分执行时间是Θ(m+n)。不过，如果计及执行匹配检查的时间,则在理论上,RK算法需要时耗Θ(mn)。但是,我们总可设法取q适当大，使得mod函数在计算机中仍可执行而冲突(即不同的字符串具有相同的散列值)又极小可能发生，而使算法的实际执行时间只需Θ(m+n)。