Z algorithm

algorithm

理解できると楽しいけど難しくて理解できないことも多い。
理解の種類で分類すると次のようになる。

  1. 概要を理解している (API が使える)
  2. 仕組みを理解している (実装できる)
  3. 様々な問題でそれを適切に使える

大抵 1 はまあ何とかなるし、それさえ分かっていればライブラリが探せるので 3 も何とかなるかもしれない。
でも 2 が分かっていると 3 の確率が上がるような気がするので何とかしたい。
そうやってもがいている間に別のことを調べていたりする。
Boyer-Moore algorithm を調べたけど O(n) の準備処理が理解できずに Z algorithm に辿り着いた。

Z algorithm の概要

s は文字列で N はその長さとする

  • s と s[i..
  • 計算量は O(N)
  • Boyer-Moore 法の準備処理にも使える
    • 各位置の prefix 長を調べるのも suffix 長を調べるのも本質的には同じ
    • z(s.reverse()).reverse() で各位置の suffix 長になる
// 次の処理を O(N) で行えるのが Z algorithm
// O(N^2)
def z(s) {
  final int N = s.size()
  def z = new int[N]
  // 1 <= i < N に関して
  for (int i = 1; i < N; i++) {
    // LCP(longest common prefix) 長を調べる
    int size = 0
    while (i+size < N && s[i+size] == s[size]) size++
    z[i] = size
  }
  return z
}

Z algorithm の仕組み

文字列処理の効率を上げることは比較回数を減らすということ。
Z algorithm では比較結果を再利用して比較回数を減らしている。
各文字位置で判断を行い3つに分類する。

  • Case 1: 比較結果を再利用できない
  • Case 2: 比較結果を再利用できる
  • Case 3: 比較結果を一部再利用できる

判断の基準は

// i-1 までの LCP長 が分かっているとする。 z = [0,1,0,2,1,...]
// 0        L   R         i=L のときの s[i..<N] 側のLCPの右端を R とする
// aabaaXXXXaabaa?...     ? は X 以外の文字
//               i        Case 1: LCP 外なので z を利用できない
//  k        i            Case 2: LCP 内なので z[i] == z[k]
//    k        i          Case 3: LCP 内だが ? 以降を確認する必要がある z[i] >= z[k]
//                                ? が b 以外の場合 z[i] == z[k]


大体理解できたので、個人的に読みやすそうなソースを選んで Groovy で書き直してみる

// O(N)
def z(s) {
  final int N = s.size()
  def z = new int[N]
  int L = 0   // LCP の左端
  int R = 0   // LCP の右端
  for (int i = 1; i < N; i++) {
    if (i > R) {
      // Case 1
      L = R = i
      while (R < N && s[R-L] == s[R]) R++
      z[i] = R-L
      R--
    } else {
      int k = i-L
      // z[k] < s[i..R].size()
      if (z[k] < R-i+1) {
        // Case 2
        z[i] = z[k]
      } else {
        // Case 3
        // R の次から照合を続ける
        L = i
        R++
        while (R < N && s[R-L] == s[R]) R++
        z[i] = R-L
        R--
      }
    }
  }
  return z
}

assert z("ABAAABAABB") == [0,0,1,1,4,0,1,2,0,0]

Case 3 のとき R の次から照合するように変更した。
O(N^2) と何回か比較したので大丈夫なはず。

計算量が O(N) なのは R の位置が戻らないから?
最悪の場合 2N 回比較するらしいがパターンが思いつかない。
s = ('A'..'Z').join('A') で 1.5N 回