この記事はデータ構造とアルゴリズム Advent Calendar 2019 21日目の記事です。
20日目は@flareさんによる「ビットコイン技術入門 2/3（データ構造・マイニング編）」です。
22日目は@allowfirmさんによる「モンテカルロ法による探索」です。
はじめに
この記事では、文字列中に出現する回文について記述します。
回文とは、右から読んでも左から読んでも同じ、アレです。
回文とは
文字列 $w$ が回文であるとは、文字列 $w$ の逆文字列 $w^R$ が文字列$w$と一致することである。
以上の定義から、この記事では１文字も回文であると定義します。
回文の例
- I
文字列中の回文
文字列中に出現する回文について考えましょう。
例えば、「しましまのしまうま」という長さ９の文字列中に回文はいくつ出現するでしょうか。
１文字も回文としているので、長さ１の文字列、し、ま、し、ま、の、し、ま、う、ま、は回文です。更に、しまし、ましま、まうま、も回文です。この例には、長さ１の回文が９つ長さ３の回文が３つの計12個の出現があります。
ここで、文字列の開始位置を含む回文（以降、接頭辞回文）について考えましょう。
例えば、「しましまのしまうま」の接頭辞回文は、「し」と「しまし」の２つです。
長さ$n$の文字列の中に接頭辞回文は最大でいくつ出現するでしょう。
答えは$n$個です。同一の文字のみからなる長さ$n$の文字列の例を想像すれば任意の接頭辞が回文になるので、$n$個出現しますね。
#回文の保持
長さ$n$の文字列中の開始位置を含む回文は最大で$n$個と言いました。では、これらの回文全てを保持するために必要な領域について考えます。
回文すべての終了位置を保持しておけば、$O(n)$で回文を保持できます。（接頭辞回文なので、開始位置は保持する必要がない）
1996年、Gasieniecらが、長さ$n$の文字列中の開始位置を含む回文は$O(\log n)$個の等差数列で保持できることを主張しました。これに基づき、この記事では、長さ$n$の文字列中の開始位置を含む回文は$O(\log n)$個の等差数列で保持できること示します。ただし、上記論文には証明がないため、2009年のMatsubaraらの論文で示された証明に基づいて書いています。
※等差数列は、初項、公差、項数の３つの数字さえ保持できればいいので、$\log n$個の等差数列は$3\log n$で保持できます。
この例だと、初項１公差２項数３（ピンク）、初項１１公差６項数２（赤）、初項３５公差０項数１（青）の３つの等差数列で接頭辞回文が保持できています。
準備
文字列$w$上の接頭辞回文の集合を$PPals(w) = {w[1..a_1], w[1..a_2],\ldots , w[1..a_k]}$とします。ここで、$w[1..s]$は$w$の長さ$s$の接頭辞とし、$a_1<a_2< \ldots <a_k$を満たすとします。また、$a_{i+1} = a_i + d_i$とします。つまり、$d$は次の回文の終端までの距離です。
補題１
$w[1..q] \in PPals(w), 1\leq i<j\leq q$を満たす任意の$i, j, q$について、$w[i..j] = w[q-j+1..q-i+1]^R$が成り立つ。
これは、$w[1..q]$が回文であることより、$w[1..\frac{q}{2}] = w[\frac{q}{2}+1..q]^R$が成り立つからです。
##補題２
任意の$a$と$d$について、$w[1..a], w[1..a+d]\in PPals(w)$かつ$a-d\geq 1$ならば、$w[1..a-d]\in PPals(w)$が成り立つ。
以下証明。
$w[1..a] \in PPals(w)$より$w[1..a-d] = w[a-(a-d)+1..a-1+1]^R = w[d+1..a]^R$
$w[1..a+d] \in PPals(w)$より$w[d+1..a] = w[(a+d)-a+1..(a+d)-(d+1)+1]^R = w[d+1..a]^R$となり、$w[1..a-d] = w[d+1..a]^R = w[d+1..a]$
よって$w[1..a-d]\in PPals(w)$
（証明終了）
ややこしい計算のように見えますが、補題１を使っているだけです。
お気づきの方もいるかもしれませんが、
同様にして、$w[1..a-d], w[1..a]\in PPals(w)$より$w[1..a-2d]$、$w[1..a-2d], w[1..a-d] \in PPals(w)$より$w[1..a-3d]$も接頭辞回文になります。
要するに、$w[1..td], w[1..(t-1)d], \ldots, w[1..d]$というふうに、回文は等差数列の形で出現するわけです。
ではこの等差数列が、$O(\log n)$個しかないことを示していきます。
##補題３
任意の$1 \leq i<k-1$について、$d_i \leq d_{i+1}$が成り立つ。
要するに、ある接頭辞回文と次に長い接頭辞回文の長さの差は、だんだん大きくなっていくよっていうわけです。
以下証明
$d_i > d_{i+1}$と仮定し、背理法で証明する。
$w[1..a_{i+1}], w[1..a_{i+2}] \in PPals(w)$つまり$w[1..a_{i+1}], w[1..a_{i+1}+d_{i+1}] \in PPals(w)$より、$w[1..a_{i+1}-d_{i+1}] \in PPals(w)$（$\because$ 補題２）
よって$a_i=a_{i+1}-d_{i+1}<a_{i+1}$
これは、$w[1..a_i]$の次に長い接頭辞回文が$w[1..a_{i+1}]$であることに反する。
（証明終了）
これで、接頭辞回文の長さの差は非減少であることがわかりました。長さの差が等しい回文が続く限りはこれらは１つの等差数列で表すことができます。よって、$d$は高々$\log n$種類しかないよということを言ってあげればいいわけです。では、高々$\log n$種類しかないことを見ていきます。
補題４
$d_i \neq d_{i+1}$のとき、$d_{i-1}+d_i \leq d_{i+1}$が成り立つ。
以下証明。
補題２より、$w[1..a_{i+1}-d_{i+1}] \in PPals(w)$。
$a_{i+1}-d_{i+1} = a_j (1 \leq j \leq i)$とおくと、
$d_{i+1} = a_{i+1} - a_j = \sum_{l=j}^{i}(a_{l+1}-a_l) = \sum_{l=j}^{i}d_l$
$d_i \neq d_{i+1}$より、$j<i$。（もし$j=i$だと、$d_{i+1}= \sum_{l=j}^{i}d_l=d_i$となり、仮定を満たさない）
以上より、$d_{i+1} = \sum_{l=j}^{i}d_l \geq d_{i-1}+d_i$
（証明終了）
ここまでで、接頭辞回文が常に（大まかには）倍以上に長くなっていくことがわかると思います。倍々で増えて行くので$O(\log n)$となるわけです。が、もう少し数学的に証明していきます。
##O(log n)個の等差数列で保持する。
再度になりますが、$d$が変わらない間は１つの等差数列で保持できます。
接頭辞回文を保持する等差数列の個数を最大化するため、初項と公差を最小化し項数を１としたとき（つまり、長さ$n$の文字列に、常に$d_i \neq d_{i+1}$を満たす接頭辞回文を詰めれるだけ詰めた場合）、接頭辞回文を保持する等差数列が何個になるかを考えます。
このとき、 $d_i = 2, 3, 5, 8, 13, \ldots$（$\because$補題４より、$d_{i+1}$の最小値は$d_i+d_{i-1}$）
ここで、フィボナッチ数列を思い出してみてください、
$F_i = 1, 1, 2, 3, 5, 8, 13, \ldots$
つまり、$d_i = F_{i+2}$となります。
よって、$a_i = a_1 + \sum_{h=1}^{i+1}F_h-F_1-F_2 = F_{i+3}-2$
また、フィボナッチ数の一般項は$F_i = \frac{\Phi ^i - (1-\Phi)^i}{\sqrt{5}}$ （$\Phi$は約$1.6$）であることが知られているので、最長の接頭辞回文$w[1..a_k]$の終了位置を計算すると
$a_k = F_{k+3}-2 = \lfloor \frac{\Phi ^{k+3}}{\sqrt{5}} + \frac{1}{2} \rfloor -2 > \lfloor \frac{\Phi ^{k+3}}{\sqrt{5}} \rfloor + \frac{1}{2}-1 -2$
$a_k \leq n$より、$k = O(\log n)$
よって、長さ$n$の文字列の接頭辞回文は$O(log n)$個の等差数列で保持できることがわかりました。
おわりに
なぜ今日、回文についての記事を書いたのかについては、カレンダーを見て頂くと容易に想像がつくかと思います。
12月21日は、宮崎二健氏によって回文の日と定められているそうです。なぜ回文の日なのかの考察は@kgotoさんの記事にあります。
回文を列挙してからちょうど３年が経ちました。
間違いや分かりづらい点など、教えていただけますと、こっそり直しておきます。
参考文献
-
Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter:
Efficient Algorithms for Lempel-Zip Encoding (Extended Abstract). SWAT 1996: 392-403 -
Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto:
Efficient algorithms to compute compressed longest common substrings and compressed palindromes. Theor. Comput. Sci. 410(8-10): 900-913 (2009)