Skip to content →

文字列

記法

自由モノイド

集合 \(\Sigma\) をアルファベットと呼ぶ。アルファベットの要素を文字と呼ぶ。文字の列を語と呼ぶ。有限長の語全体を \(\Sigma^*\)、長さ \(n\) の語の集合を \(\Sigma^n\) と置く。語 \(s, t\) の結合を \(st\) と書く。また、空語を \(\varepsilon\) と置く。空語は結合の単位元である。空語は辞書順最小とする。結合は結合法則を満たすので、\(\Sigma^*\) 上でモノイドをなす。このモノイドを自由モノイドと呼ぶ。

その他

逆順にした語を \(s^R\) と置く。辞書順で \(s\) の方が \(t\) より小さいとき \(s \prec t\) と書く。語 \(s\) の \(i\) 文字目を \(s[i]\) と表す。\([i..j] = \{i, i+1,\ldots,j\}\)、\(s[i..j]=s[i]s[i+1]..s[j]\)と置く。語 \(s,t\) の連結を \(st\) と書く。語 \(s\) の長さを \(|s|\) と書く。空語を除いたものを \(\Sigma^+=\Sigma^*-\varepsilon\) と置く。語 \(w\) が語 \(x\) の接頭辞であるとき、\(w <_{suf} x\) と書く。また、語 \(w\) が語 \(x\) の真の接尾辞であるとき、\(w <_{pref} x\) と書く。\(t\) が \(s\) の部分語のとき、\(t \subset s\) と書く。語 \(s, t\) の最長共通接尾辞を \(\mathrm{lcp}(s, t)\) と書く。\(\xi s\) を \(s\) の真の suffix のうち最も長い語とする。語の集合 \(A\) に対して、\(\xi_A s\) を、 \(A\) に含まれる語の suffix のうち \(s\) の真の suffix であって、最も長い語とする。アルファベットまたは一文字の語を \(\sigma\) と書く。語 \(s\) を無限回接続した語を \(s^\omega\) と置く。

語の周期

\(s[i] = s[i \bmod d]\) が成り立つとき、\(s\) の周期は \(d\) であるという。そのような最小の正整数を \(w\) の最小周期と呼び、\( \mathrm{period}(s)\) と置く。\(\mathrm{ord}(s) = \mathrm{period} / |s| \in \mathbb{Q}\) を \(s\) の位数と呼ぶ。\(s = u^{\mathrm{ord}(s)}\) を満たす \(u\) が存在する。\(s\) の接頭辞かつ接尾辞である真部分語 \(u\) を \(s\) の境界と呼ぶ。周期の定義を同値変形することにより、
\begin{align}
&s[i] = s[i \bmod d]\\
\Leftrightarrow&s[i]=s[i+d] \quad (1 \leq i \leq |s|-d)\\
\Leftrightarrow& s[1..|s|-d-1] = s[d+1..|s|] \\
\end{align}となるので、境界を \(b\) とすると $$|s|-|b|$$ は周期である。別証明として、\(s=ax=xb\) ならば
\begin{align}
a^ix &= a^{i-1}xb \\
&=a^{i-2}xb^2 \\
&=xb^i
\end{align}より \(a^\omega=xb^\omega\) から、周期 \(|a|=|b|=|s|-|x|\) が分かる。語 \(s\) の最長境界を \(\mathrm{Border}(s)\) と置きます。境界は長い順に \(\mathrm{Border}(s), \mathrm{Border}^2(s), \ldots, \mathrm{Border}^k(s) = \varepsilon\) と列挙できます。境界の長さを \(\mathrm{border}(s)\) と置きます。\(s\) の周期は降順に \(|s|-\mathrm{border}(s),|s|-\mathrm{border}^2(s),|s|-\mathrm{border}^3(s),\ldots, |s|-\mathrm{border}^k(s)=|s|\) で全てである。\(\mathrm{period}(x) = |x| – \mathrm{border}(x)\) である。

FineとWilfの定理

語 \(s\) が周期 \(p\) かつ周期 \(q\) かつ \(|s| \geq p + q-\gcd(p, q)\) ならば、周期 \(\gcd(p, q)\) である。
証明:\(s = u^{\gcd(p, q)}\) と書けるので、\(u\) の周期を考えることで、\(p, q\) が互いに素な場合に帰着できる。また、\(|s|=p+q-1\) の場合だけ示せば十分。\(p = 0 \lor q = 0 \lor p = q\) ならば明らか。\(q < p\) とする。\(1 \leq i \leq q-1\) では \(s[i]=s[i+p]=s[i+p-q]\) なので、\(a=s[1..p-1]\) は周期 \(p-q\) である。\(|a| = p-1 = (p-q) + q-1\) だから帰納法が回る。

次のようにしてもよい。長さ \(q-1\) の境界を \(q\) だけ移動することで、\(s[1..p-1]\) は長さ \(q-1\) の境界を持つことが分かる。従って、\(s[1..p-1]\) は周期 \((p-1)-(q-1)=p-q\) を持つ。

別証明として、\(\sum s[i]t^i\) という形式的べき級数を考える方法もある(省略)。

例えば、\(ab = ba\) と表せる語 \(s\) は周期 \(|a|, |b|\) で \(|s| \geq |a|+|b|-\gcd(|a|, |b|)\) なので周期 \(\gcd(|a|, |b|)\) である。\(\gcd(|a|, |b|)\) は \(|s|\) の約数なので、\(s\) はある整数乗で表せる。

Fine–Wilfの定理から、\(|s|\) の非自明な約数を周期に持つならば、最小周期もまた非自明な約数になることが分かる。

周期のGCDが取れない例(フィボナッチ語)

\(f_0 = a, f_1 = b, f_i=f_{i-1}f_{i-2}\) とする。
\(\phi(f_0)=f_1, \phi(f_1)=f_2\) を満たす準同型写像すなわち \begin{align}
\phi(a)&=b \\
\phi(b)&=ba
\end{align}は\(\phi(f_i)=f_{i+1}\)を満たす。順に計算することで、\(n \geq 1\) のとき $$f_n = f_1f_2\cdots f_{n-2}$$ が成り立っていること分かる。\(f_n\) の後ろ2文字を削った文字列を \(g_n\) とすると、\(g_n\) は周期 \(|f_{n-1}|, |f_{n-2}|\) を持つ。これは
\begin{align}
&g_n <_{pref} f_{n-1}f_{n-2} <_{pref} f_{n-1}^2 \\
&g_n = f_{n-1}g_{n-2} = f_{n-2} f_{n-3}g_{n-2} <_{pref} f_{n-2}^2
\end{align}から分かる。\(g_n\) は Wine–Wilf の定理で周期の gcd が取れないギリギリの例を与えている。

累乗

\(s = w^m\) \( (m \in \mathbb{N}, m \geq 2)\) と表すことができないような語を原始的と呼ぶことにする。語 \(s\) を \(n\) 回繰り返した \(s^n\) について考察したいとする。このとき、原始的な語 \(w\) を用いて \(s = w^m\) と一意に書けるので、\(s^n = w^{nm}\) とできる。

累乗で表される回文

語を逆順にする関数 \({\cdot}^R\) は反準同型写像 \((xy)^R=y^Rx^R\) なので、\((w^n)^R = (w^R)^n\) である。つまり、\(w^n\) が回文ならば \(w\) は回文になる。

共役

語 \(x, y\) について、ある語 \(a, b\) を用いて \(x = ab, y=ba\) と表せるとき、\(x, y\) は共役であると呼ぶ。\(x, y\) が共役であることと、\(gx=yg\) を満たす \(g\) が存在することは同値である。\(\Rightarrow\) は \(x=uv, y=vu\) とすると、\(vx=yv\) であることから分かる。\(\Rightarrow\) は \(\forall i\in\mathbb{N}, gx^i=y^ig\) より \(gx^\omega=y^\omega\) だから、\(x\) は \(y\) の巡回シフトになることから分かる。これは群の \(x = aya^{-1}\) のアナロジーである。共役な語は、巡回シフトで移り合う。従って、共役な語は同値類をなす。この共役類をネックレスと呼ぶ。共役類の大きさは整数の位数と等しい。従って、原始的な語の共役類の大きさは語長と等しい。

巡回置換作用を \(D\) とすると
\(ss = D^d(ss)\)
ならば \(|s|\) は周期 \(\gcd(|s|, d)\) を持つ(yuki1018)。

KMP法

接頭辞の最長境界を列挙するアルゴリズムである。\(\mathrm{Border}(s\sigma)\) は \(s\) の境界 \(\mathrm{Border}^1(s), \mathrm{Border}^2(s), \ldots, \mathrm{Border}^k(s) = \varepsilon\) のうち、\(s[|\mathrm{Border}^i(s)|+1] = \sigma\) となる最長のものを(存在するなら)用いて、\(\mathrm{Border}(s\sigma) = \mathrm{Border}^i(s)\sigma\) と書ける。存在しなければ、\(\mathrm{Border}(s \sigma) = \varepsilon\) となる。境界は接尾辞で、\(\mathrm{Border}^{i}(s)\) は \(B^{i-1}(s)\) の最長境界であるから、\(\mathrm{Border}^i(s)\) は全て計算済みである。\(s\sigma\) の最長境界は \(s\) の最長境界に比べて高々一つしか長さが増加せず、最長境界は再帰的に取るたびに長さは単調減少するので、ならし \(O(1)\) で最長境界を列挙できる。

高速化

\(\mathrm{period}(s) \leq |s| / 2\) ならば、\(\mathrm{period}(s)\) の倍数でない \(p\) は周期は、\(|s|/2\) 超である。さもなくば、Fine–Wilfの定理より \(\gcd(\mathrm{period}(s), p)\) の周期があるが、これは最小性に反する。言い換えれば、\(s=(uv)^ku\) \((k\geq1, u \in \Sigma^+)\) の境界は
\(w=uv\) と置くと、
$$w^{k-1}u, w^{k-2}u, w^{k-3}u, \ldots$$
の形が長さ \(|s|/2\) 以上である間は続く。この形は全て \(s[\mathrm{Border}^i(s)+1] = u[1]\) であるから、\(\sigma \neq u[1]\) ならば計算を飛ばすことができる。従って、ならし計算量が実時間 \(O(\log(|s|)\) にできる。

辞書順

\(S,T \in \Sigma^+\) について \( \overline {S <_{suf} T}\) ならば
\(S \prec T \Rightarrow SA \prec TB\) である。この事実より、\(S, T\) の順序から \(SA,TB\) の順序が定まらないのは \(S <_{suf} T\) または \(T <_{suf} S\) のときのみである。(yuki1018, ARC058F)lcp が求まれば、辞書順も分かる。

\(A \prec B \Leftrightarrow \mathrm{lcp}(A)^{-1}A \prec \mathrm{lcp}(B)^{-1}B\)

である。

prefix の列 \(s_1 <_{pref} s_2 <_{pref} \cdots <_{pref} s_n\) と語 \(t\) について、\(\{s_i\}
\cup \{s_i t\}\) を辞書順に並べよ。(ARC058C)
\(s_it < s_jt\) \((i < j)\)
\(\Leftrightarrow t< s_i^{-1}s_jt\) \((i < j)\)

などから \(t\) と \(s_i^{-1}s_j\)、\(t[|s_i^{-1}s_j|+1..|t|]\) と \(t\) の比較などに帰着できる。

回文

\(s\) が回文 \(\Leftrightarrow\) \(s[i] = s[|s|+1-i]\) である。\(s\) が回文ならば \(s[l..r] = s[|s|+1-r..|s|+1-l]\) である。特に、\(s,s[l..r]\) が回文ならば、\(s[|s|+1-r..|s|+1-l]\) は回文である。

部分語に含まれる回文の種類数の上限

S に部分語として含まれる回文の種類数は |S| 個以下である(ABC237H)。これはManacherのアルゴリズムから分かる。\(S[a..|s|]\) と \(S[b..|s|]\) \((a < b)\) が回文ならば \(s[b..|s|] = s[a..|s|-b+a] \subset s[1..|s|-1]\) より長さを一つ増やすごとに回文の種類数が高々一つしか増えないことからもわかる。

LCS

\(\mathrm{lcs}(s, s^R)\) の長さは、 \(s\) の部分語の回文の最大の長さに等しい(AGC021D)。

語の長さの種類数

語 \(t_1, t_2, \ldots, t_n\) の長さの合計が \(n\) で抑えられるならば、長さの種類数は \(O(\sqrt{n})\) である。これは \(\sum_{i=1}^k i = k(k+1) /2 \leq n\) のとき \(k = O(\sqrt n)\) であることから従う。この事実によりDPなどを高速化できることがある。例えば、Aho-Corasick 法で \(A = \{t_1, t_2, \ldots, t_n\}\)、語長の和が \(\sum |t_i| \leq n\) とする。\(\xi’_A s\) を \(A\) のうち \(s\) の suffix であるものとすると、\(\xi’_As\) はメモ化によりならし \(O(1)\) で求まる。\(|t_i|\) の種類数が \(O(\sqrt{n})\) であること、\(\xi_A’\)を掛けるたびに長さが狭義単調減少することから \(O(\sqrt{n})\) 回掛けると \(\varepsilon\) になる(ECR097G)。\(\zeta_A s\) をキーとしたDPができる(AOJ2257)。オンラインに文字を追加すると、$\zeta_A $ の最長性が破壊されるため、基本的にはオフラインでしか使えない。要素列に対して演算が準同型ならば、\(\log(n)\) のオーバーヘッドによりオンラインにできる(ECF710F)。

Trie

語の末尾への incremental な更新があり、オフラインで処理してよい場合、最終的な語の集合に対する Trie を構築することでほかの種類のクエリが処理できるようになることがある。例えば、\(\sum_i|\mathrm{lcp}(S_i, S_k)|\) を求めるクエリ(yuki2020)。

Aho-Corasick法

次のようなことができるデータ構造。

  • \(s \in \mathrm{prefix}(A)\) である語 \(s\) に対して \(s\sigma\in \mathrm{prefix}(A)\) かどうかが \(O(\log \Sigma)\) で求まる。
  • \(s \in \mathrm{prefix}(A) \) に対して \(\xi_As[1..i]\) が \(O(1)\) で求まる。

KMP法を複数の語に対して拡張したアルゴリズムと捉えられる。\(\xi_As[1..i]\) は語長の昇順に列挙できて、KMP法と同様の理屈で \(O(\sum_{s \in A}|s|)\) 時間になる。

回文木

語 \(s\) 中の unique な回文に対して、Aho-Corasick法と同様のことをする。

Zアルゴリズム

(長さ、アルファベット)を一つのアルファベットとして扱ったZアルゴリズムができる。特に、連長圧縮した語に対するZアルゴリズムは、両端を特別に処理することで、連長圧縮後の長さに対して線形で動作する(yuki1848)。Manacherも線形でできるはず。

語の分割

語 \(s\) を \(s=s_1s_2s_3s_1s_3\) の形で表す方法が何通りあるか求めよ(ARC055C)

語 \(s\) は最小で何個の \(s\) の prefix の連結で表せるか求めよ(ABC257G)

末尾から suffix かつ prefix である最長の語を取り除いていくのが最適。

コード

\(N = N^{-1}N \cap N N^{-1} \Leftrightarrow \) \(N\) は自由

\(N = N^{-1}N\cap N N^{-1}\) の極小な生成元の集合の一例は \(X = N-\varepsilon-(N-\varepsilon)^2\) と表せる。\(X\) がコードでないとすると、ある \(x_i, y_i \in X\) が非自明な関係式 $$x_1x_2 \cdots x_n
= y_1 y_2 \cdots y_m$$
を満たす。語の長さが最小とする。極小性より \(x_1 \neq y_1\) である。\(|x_1| < |y_1|\) としても一般性を失わない。\(y_1 = x_1w\) とすると、
\begin{align}
w &= x_1^{-1}y_1 \in N^{-1}N\\
&= (x_2x_3\cdots x_n)(y_2y_3\cdots y_m)^{-1} \in N N^{-1}\\
\end{align}
である。従って、\(w \in N – \varepsilon\)であるから、\(y_1 \not\in (N-\varepsilon)^2\) に反する。従って、\(X\) はコードになり、\(N\) は自由になる。逆に \(N\) が自由として、コードを \(X\) とする。\(\varepsilon \in N^{-1} \) だから \(NN^{-1} \cap N^{-1}N \supset N\) は明らかである。\(\subset\) を示せばよい。つまり、\(ab, ca, b, c \in N \) ならば \(a \in N\) であることを言えばよい。\(c(ab) = (ca)b \in N\) について、両側からコードを比較して削っていくと、\(a\) が残るので、\(a \in N\) である。

  • \(N = NN^{-1} \Leftrightarrow\) 接尾辞コード
  • \(N = N^{-1}N \Leftrightarrow\) 接頭辞コード
  • \(N = N^{-1}N = NN^{-1}\Leftrightarrow\) 両接コード

\(N = NN^{-1} \Leftrightarrow\) 接尾辞コード を示す。\(\Rightarrow\) を示す。\(xy \in N, y \in N\) ならば \(x \in N\) だから \(xy\) はコードに含まれ得ない。従って、接尾辞コードである。\(\Leftarrow\) を示す。\(\varepsilon \in N^{-1}\)だから\(N \subset NN^{-1}\)は明らか。\(\supset\) を示せばよい。\(ab, b \in N\) について、\(ab\) の接尾辞側から削ると \(a \in N\) となる。接頭辞コード、両接コードも同様に示せる。

  • $(uv, vu \in N \Rightarrow u, v \in N) \Leftrightarrow$ 環状コード
  • 環状コードには共役な語は含まれない。なぜなら、\(ab, ba\) が環状コードに含まれているならば、\((ab)(ab)\) と \((ba)(ba)\) は共役で二通りの分解あるからである。

    Published in データ構造

    Comments

    コメントを残す

    メールアドレスが公開されることはありません。

    CAPTCHA