Help us understand the problem. What is going on with this article?

回文を保持する

この記事はデータ構造とアルゴリズム Advent Calendar 2019 21日目の記事です。

20日目は@flareさんによる「ビットコイン技術入門 2/3(データ構造・マイニング編)」です。
22日目は@allowfirmさんによる「モンテカルロ法による探索」です。

はじめに

この記事では、文字列中に出現する回文について記述します。
回文とは、右から読んでも左から読んでも同じ、アレです。

回文とは

文字列 $w$ が回文であるとは、文字列 $w$ の逆文字列 $w^R$ が文字列$w$と一致することである。
以上の定義から、この記事では1文字も回文であると定義します。

回文の例

  • I
    定義より、1文字も回文であるとしました。最も短く"狭い"回文はこれではないでしょうか。
  • 142+382×567=765×283+241
    式が成り立っているところが、かっこいいです。

文字列中の回文

文字列中に出現する回文について考えましょう。
例えば、「しましまのしまうま」という長さ9の文字列中に回文はいくつ出現するでしょうか。
1文字も回文としているので、長さ1の文字列、し、ま、し、ま、の、し、ま、う、ま、は回文です。更に、しまし、ましま、まうま、も回文です。この例には、長さ1の回文が9つ長さ3の回文が3つの計12個の出現があります。

ここで、文字列の開始位置を含む回文(以降、接頭辞回文)について考えましょう。
例えば、「しましまのしまうま」の接頭辞回文は、「し」と「しまし」の2つです。
長さ$n$の文字列の中に接頭辞回文は最大でいくつ出現するでしょう。
答えは$n$個です。同一の文字のみからなる長さ$n$の文字列の例を想像すれば任意の接頭辞が回文になるので、$n$個出現しますね。

回文の保持

長さ$n$の文字列中の開始位置を含む回文は最大で$n$個と言いました。では、これらの回文全てを保持するために必要な領域について考えます。
回文すべての終了位置を保持しておけば、$O(n)$で回文を保持できます。(接頭辞回文なので、開始位置は保持する必要がない)

1996年、Gasieniecらが、長さ$n$の文字列中の開始位置を含む回文は$O(\log n)$個の等差数列で保持できることを主張しました。これに基づき、この記事では、長さ$n$の文字列中の開始位置を含む回文は$O(\log n)$個の等差数列で保持できること示します。ただし、上記論文には証明がないため、2009年のMatsubaraらの論文で示された証明に基づいて書いています。
※等差数列は、初項、公差、項数の3つの数字さえ保持できればいいので、$\log n$個の等差数列は$3\log n$で保持できます。

image.png
この例だと、初項1公差2項数3(ピンク)、初項11公差6項数2(赤)、初項35公差0項数1(青)の3つの等差数列で接頭辞回文が保持できています。

準備

文字列$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$は次の回文の終端までの距離です。image.png

補題1

$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$が成り立つからです。image.png

補題2

任意の$a$と$d$について、$w[1..a], w[1..a+d]\in PPals(w)$かつ$a-d\geq 1$ならば、$w[1..a-d]\in PPals(w)$が成り立つ。
image.png
以下証明。
$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)$

(証明終了)

ややこしい計算のように見えますが、補題1を使っているだけです。

お気づきの方もいるかもしれませんが、
同様にして、$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)$個しかないことを示していきます。

補題3

任意の$1 \leq i<k-1$について、$d_i \leq d_{i+1}$が成り立つ。

要するに、ある接頭辞回文と次に長い接頭辞回文の長さの差は、だんだん大きくなっていくよっていうわけです。
image.png

以下証明
$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$ 補題2)
よって$a_i=a_{i+1}-d_{i+1}<a_{i+1}$
これは、$w[1..a_i]$の次に長い接頭辞回文が$w[1..a_{i+1}]$であることに反する。
(証明終了)

これで、接頭辞回文の長さの差は非減少であることがわかりました。長さの差が等しい回文が続く限りはこれらは1つの等差数列で表すことができます。よって、$d$は高々$\log n$種類しかないよということを言ってあげればいいわけです。では、高々$\log n$種類しかないことを見ていきます。

補題4

$d_i \neq d_{i+1}$のとき、$d_{i-1}+d_i \leq d_{i+1}$が成り立つ。
以下証明。
補題2より、$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$が変わらない間は1つの等差数列で保持できます。
接頭辞回文を保持する等差数列の個数を最大化するため、初項と公差を最小化し項数を1としたとき(つまり、長さ$n$の文字列に、常に$d_i \neq d_{i+1}$を満たす接頭辞回文を詰めれるだけ詰めた場合)、接頭辞回文を保持する等差数列が何個になるかを考えます。
このとき、 $d_i = 2, 3, 5, 8, 13, \ldots$($\because$補題4より、$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さんの記事にあります。
回文を列挙してからちょうど3年が経ちました。

間違いや分かりづらい点など、教えていただけますと、こっそり直しておきます。

参考文献

  • 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)

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away