字符串的改进模式匹配算法

字符串改进模式匹配算法计算公式:

next(j)直观含义,[0, j-1]中前缀和后缀相等的最大长度。

next(j)的直观作用,可滑过j-next(j)位不用匹配。

next(j)=-1,表示匹配失败,T的指针加1,P的指针指向p[0]。

next(j)=k+1,表示匹配失败时,P的指针指向p[k+1]。

next(j)=0,表示匹配失败时,P的指针指向p[0]。

通过j-next(j)可以计算出可以滑过多少位,而位使用以上三句话又可以计算出滑过后所需要比较的位的位置。

假设已知next(j)=x,现在计算next(j+1)

若px=pj,则next(j+1) = x+1 = next(j)+1

否则,设next(x)=h,(此时有p[0,h-1]=p[x-h,x-1]=p[j-h,j-1])

若ph=pj,则next(j+1) = h+1

否则,令next(h)=t, (此时有p[0,t-1]=p[h-t,h-1]=p[j-t,j-1])

继续判断是否pt=pj,直到找到或者到next(0) = -1

……

未经允许不得转载:TacuLee » 字符串的改进模式匹配算法

赞 (0)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址