一周一算法—— zblock算法

#技术 #算法

同上次的kmp算法,zblock算法也是用于精确字符串匹配的算法,其时间复杂度为O(m+n).

其实不论是上次讨论的kmp算法,还是下一次将要讨论的BM算法,都涉及到一个对模式串的预处理问题, 预处理的主要目的就是为了找出模式串中的一些公共的特性以在与目标串进行匹配过程中,不匹配出现时,进行 字符串的跳转时能够很好的利用这些性质,以更快的跳转的合适的位置,从合适的位置开始重新比较, 以减少不必要的重复比较,从而达到提升算法的性能的目的。其中kmp算法利用的是前辍,而BM算法利用的是 后辍。而本次讨论zblock算法的目的,主要的不是其的字符串匹配中的使用,更多的是在进行模式串预处理时 的算法思想,一是更好的解释kmp算法的next数组的计算,二是为下一次将要讨论的BM算法的预处理过程进行 知识准备。

###ZBLOCK定义

定义: 假设模式串为S[1…n],若k为使S[1…k-1]=S[i…i+k-1]的最大值,则可设 Zi[S]=k, S[i…i+k-1]即为串S的一个Zblock.

如,若模式串为S=aabcaabxaaz,则有:

  • Z5(S)=3,aabcaabxaaz
  • Z6(S)=1,aabcaabaaz
  • Z7(S)=Z8S=0,当S[i]!=S[1]时Zi(S)=0
  • Z9(S)=2,aabcaabxaaz

如下示为,为一模式串的Zblock示意,模式串可能会存在n个Zblock,且各个Zblock间是可以相互重叠的。 zblock_0 在上图中,还涉及到li,ri的定义,li, ri为指所有包含S[i]字符的Zblock中具有最大的ri的li, ri的组合。

###ZBLOCK长度的计算

Zblock长度的计算实际是通过迭代的方式完成的,假设k为S的任意位置,r为已经计算出的Zblock所覆盖位置 的最右值,l的对应r值的开始位置。那么对于k从2开始,直到S串结尾,则计算Zk[S],可分以下三种情况进行讨论:

  1. k > r : 此时由于k已经超出了已经计算的Zblock的覆盖的最右的位置,因此前面计算的所有Zk’[S]实际上此时都没 有利用价值,需要一个一个比较S[1…n]与S[k…n], 直到出现j, 使得S[j] != S[k+j-1], 那么Zk[S]=j;
  2. k <= r: 此时已可以利用之前计算的Zblock的信息. 现在假设包含S[k]的最右的Zblock为S[l…r],那么就存在 S[1…r-l+1]=S[l…r]. 那么就必定有S[k…r]会在S[1…r-l+1]区间内,有S[k’…r-l+1]与之相等。 而根据迭代过程,这个Zk’[S]的值属于已经计算过的已知值。也就是存在j, 使得S[1…j]=S[k’…k’+j-1]. 为此就可以利用这性质,计算Zk[S]的值不过又需要分两种情况讨论:
    • 当 k’+j-1 < r-l+1时, S[k’…k’+j-1]必定在S[l…r]内,其对比性质完全是可以代表Zk[S]的,所以有Zk[S]=Zk’[S] 如下图示: zblock_1
    • 当 k’+j-1 >= r-l+1时,S[k’…r-l+1]=S[k…r]=S[1…r-k+1].但是对于S[r-l+1]后的对比情况却是未知的,因此 需要继续从S[r+1]与S[r-k+2]开始一个一个进行对比,直到出现j, 使得S[j] != S[k+j-1], 那么Zk[S]=j, 相较于情况1, 此处缩短了对比的距离。 zblock_2

如若模式串为S=”aabaabcaxaabaabcy”,则其计算出的Zi(S)值可如下示:

            1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  
        S   a   a   b   a   a   b   c   a   x   a   a   b   a   a   b   c   y  
    Zi(S)   0   1   0   3   1   0   0   1   0   6   1   0   3   1   0   0   0  

###ZBLOCK字符串精确匹配的应用

Zblock算法在字符串的精确匹配时,需要做一些处理,即将模式串加上分隔符后放于目的串前面。如若模式串为 S=”aabc”, 目的串为 D=”fdafdsafdadjkdjdaabcaabx” , 分隔符为 “$”, 则处理后的串为:

aabd$fdafdsafdadjkdjdaabcaabx

这样,对上述串求取Zblock即可,在求取的Zblock的长度大于4的即为匹配的字符串。
因此,ZBlock算法进行精确字符串匹配的的时间复杂度为O(m+n).