Skip to content →

文字列

記法

\(s\) を逆順にした文字列を \(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|\) と書く。空語を \(\varepsilon\) と置く(辞書順最小とする)。アルファベット \(\Sigma\) 上の長さ \(n\) の文字列の集合を \(\Sigma^n\) と置く。有限長の文字列全体を \(\Sigma^*\) と置く。空語を除いたものを \(\Sigma^+=\Sigma^*-\varepsilon\) と置く。語 \(w\) が語 \(x\) の接頭辞であるとき、\(w \subset_{\mathfrak{s}} x\) と書く。また、語 \(w\) が語 \(x\) の接尾辞であるとき、\(w \subset_{\mathfrak{p}} 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\) と書く。

文字列の周期

\begin{align}
&s[i] = s[i \bmod d]\\
\Leftrightarrow&s[i]=s[i+d] \\
\Leftrightarrow&s[1+d..|s|]=s[1..|s|-d-1] \\
\Leftrightarrow&s[1+d..|s|] \subset_{\mathfrak{s}} s \\
\Leftrightarrow&s[0..|s|-d-1] \subset_{\mathfrak{p}} s
\end{align}

ある長さ \(d\) の文字列 \(w\) を用いて \(s=w^n\) と書けることと同値ではないことに注意。

巡回置換作用を \(D\) とすると

\begin{align}
&ss = D^d(ss) \\
\Leftrightarrow &s[i] = s[i \bmod \gcd(|s|,d)] \\
\Leftrightarrow &s = w^{|s|/\gcd(|s|,d)} \\
\end{align}と書ける(yuki1018)。

KMP法

\(\xi^{k}s\) は真の suffix のうち \(k\) 番目に長い文字列である。

\begin{eqnarray}
\left\{
\begin{array}{l}
\xi^k s[0..i]=s[0..t] \\
s[i+1]=s[t+1]
\end{array}
\right.
\end{eqnarray}を満たす最小の \(k\) (\(k’\)と置く)を用いると、\(\xi s[0..i+1]=s[0..t+1]\) となる。\(\xi\) を掛けると長さは狭義単調減少する。また、\(|\xi^{k’}s[0..i]| + 1 = |\xi s[0..i+1]|\) なので、各 \(1 \leq i \leq |s|\) について \(k’\) を列挙する(\(\xi s[0..i+1]\) を求める)ことは \(O(|s|)\) でできる。

高速化

\(\xi s[0..i] = s[0..j] = s[i-j..i]\) ならば、\(s[0..j]\) は周期 \(i-j\) を持つ。つまり、長さ \(i-j\) の文字列 \(w\) を用いて \(s[0..i]=w^{m}[0..j)\) と書ける。上記の \(k’\) の計算が \(O(\log(i))\) にできる。

累乗

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

累乗で表される回文

\(s = w^n\) が回文ならば、(\(n\)の偶奇の依らず) \(w\) は回文である。

辞書順

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

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

である。

prefix の列 \(s_1 \subset_{\mathfrak p} s_2 \subset_{\mathfrak p} \cdots \subset_{\mathfrak p} 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 である最長の文字列を取り除いていくのが最適。

Published in データ構造

Comments

コメントを残す

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

CAPTCHA