字符串匹配-Z算法

Z 算法

对于长度为n的字符串s，定义函数z[i]表示字符串本身s和其后缀s[i, n-1]的最长公共前缀长度(LCP, longest common prefix)。 z被称为s的z函数。z[0]=0。计算z数组的方法一般被称为Z-Algorithm，也称为扩增KMP算法。

• Z函数的朴素实现方式 朴素实现方式的复杂度为O(n^2)， for循环和while循环两层， 举一个最极端的例子，s='aaaaa'， 很明显每次while循环在每一个i时都会遍历全部的z，长度也为n，故朴素算法的时间复杂度为O(n^2)。

def z_function_trivial(s):
    n = len(s)
    z = [0] * n # 最长公共前缀的长度(s和其后缀)
    for i in range(1, n):
        # 索引正常 同时 *s前缀*和*s后缀的前缀*相同
        while i + z[i] < n and s[z[i]] == s[i+z[i]]:
            # 在i位置，s和s[i, n-1]的最长公共前缀的长度，相同+1
            z[i] += 1
    return z

# 举例子
# s = 'abaab'
# n = 5
#                                                           z[0] = 0
# i = 1, s = 'abaab', s的后缀s[1:4] = 'baab', 两者的LCP为0, z[1] = 0
# i = 2, s = 'abaab', s的后缀s[2:4] = 'aab' , 两者的LCP为1, z[2] = 1
# i = 3, s = 'abaab', s的后缀s[3:4] = 'ab'  , 两者的LCP为2, z[3] = 2
# i = 4, s = 'abaab', s的后缀s[4] = b       , 两者的LCP为3, z[4] = 0

• Z函数线性算法

对于字符串匹配，要想提速匹配过程，必须利用前面匹配好的数组，不然达不到加速的目的。 对于特定的i, 我们称区间[i, i + z[i]]是i的匹配段，称为Z-box。 算法中，我们维护右端点最靠右的匹配端。记作[l, r]。根据定义，s[l, r]是s的前缀。在计算z[i]，我们保证l<=i。 初始化时，l=r=0。

def z_function(s):
    n = len(s)
    z = [0] * n 
    l, r = 0, 0 
    for i in range(1, n):
        if i <= r and z[i -l] < r -l + 1:
            z[i] = z[i - l]
        else:
            z[i] = max(0, r - i + 1) # 关键加速步骤
            # 朴素算法
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

复杂度分析: 对于内层的while循环，每次执行都会使得r向后移动至少1位，由于r<n-1所以总共会执行n次。 对于外层循环，只有一次线性遍历。总复杂度为O(n)。

应用场景

• 匹配所有子串

  def zMatch(p, t):
      s = p + '$' + t
      Z = z_function(s)
      occurrences = []
      for i in range(len(p) + 1, len(s)):
          if Z[i] >= len(p):
              occurrences.append(i - (len(p) + 1))
      return occurrences

$ zMatch('abcdabcd', 'abcdefghijklabcdabcd')
$ [12]