記法

自由モノイド

集合 \(\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の定理

周期 \(p\) より \(p\) 個の同値類に分かれる。これらが一つになるには、少なくとも \(p-1\) 個の別の独立な同値関係が必要である。周期 \(q\) を用いて、先頭から \(i\) 文字目と \(i+q\) 文字目が等しいという関係を \(i = 1, \ldots, p-1\) について加えるには少なくとも全体の文字列の長さが \(p + q – 1\) 以上でなければならない。

別証明として、\(\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\) の後ろ２文字を削った文字列を \(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]\) より長さを一つ増やすごとに回文の種類数が高々一つしか増えないことからもわかる。\(AB=B^RA^R, BA=A^RB^R\) が成り立つとする。\begin{align}
A^RABB^R&=BAA^RB^R \\
&=BABA\\
&=BB^RA^RA
\end{align}
従って、\(A^RA,BB^R\) は互いに可換だから、欠陥定理よりある一意な原始的な語 \(u\) に対して、\(A^RA,BB^R \in u^*\) である。\(A^RA,BB^R\) は回文であるから、\(u\) も回文である（kumaさんのブログ）。

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)\) であることから従う。このことから、長さ n の文字列に含まれる部分文字列の種類数は \(O(n \sqrt{n})\) である。また、この事実によりDPなどを高速化できることがある。例えば、Aho-Corasick 法で \(A = \{t_1, t_2, \ldots, t_n\}\)、語長の和が \(\sum |t_i| = O( 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）。パターン数を2進数で表した時のビットが立っている桁ごとに Aho-Corasick を用意する。繰り上がりの回数が \O(\log(n))\) で抑えられる。

• パターン\(P_1, P_2, \ldots, P_n\) が事前に与えられる。文字列 \(S_1, S_2, \ldots, S_m\) が与えられるので、それぞれ、オンラインでパターンが部分文字列として何回現れるか求めよ。\(N = \sum |P_i|, M = \sum |S_i|\) として \(O(N+M)\)。
• 文字列とパターンがオンラインで与えられる。パターンは追加と削除がある。各文字列に対して、パターンが部分文字列として何回現れるか求めよ。\(O((N+M) \log(n))\)。
• パターン \(P_1, P_2, \ldots, P_n\) と文字列 \(S\) が与えられる。パターンとマッチしないようにするには、\(S\) から何文字削除する必要があるか。\(O(|S|\sum |P_i|)\)
• 削除ではなく文字の変更だとどうなるか？
• 文字列 S, パターン P_1, .., P_n, 整数列 a_1, .., a_n が与えられる。Sの部分文字列であって、P_iをa_i回含むものの、最短の長さをそれぞれ求めよ\(O(|S|\sqrt{|S|}\log(|S|))\)（CF963D）
• 文字列S_1, S_2, .., S_nが与えられられる。文字列Tをこれらの文字列のオーバーラップ（糊しろを持たせてつなげる）で表すには何個必要か。同じ文字列を複数回使っても良い。Aho-Corasickと貪欲法で\(O(|T|+\sum|S_i|)\)（joi2010day2）

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）

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

コード

\(X^*\) が \(X\) の要素の積として一意にかけるとき、\(X\)をコードと呼ぶ。

\(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\) 接尾辞コード を示す。\(\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\) となる。接頭辞コード、両接コードも同様に示せる。

環状コードには共役な語は含まれない。なぜなら、\(ab, ba\) が環状コードに含まれているならば、\((ab)(ab)\) と \((ba)(ba)\) は共役で二通りの分解あるからである。
01 列 a, b について、a と b[s..|s|] で 1 が同じ場所にあるのは Σa[i]b[i+s] 箇所である。これは畳み込みの形をしているので、FFTで各sについて列挙できる。各アルファベットについて個別に処理することで、マッチしている文字数の最大化に使える。文字の種類数|Σ|が大きいときは、登場回数√(nlog(n))以上かどうかで愚直に計算するかFFTで計算するか場合分けすると良い。n/√(nlog(n))回しかFFTしないのでO(n^{1.5}\sqrt{\log(n)})になる。

01以外の場合、完全にマッチングしているかどうかはΣ(a[i]-b[i+s])^2がゼロかどうかで分かる。Σ(a[i]-b[i+s])^2=Σa[i]^2 + Σb[i+s]^2 -2Σa[i]b[i+s] の1, 2項目は簡単に計算できる。3項目は畳み込みの形をしているのでFFT。

文字 0 を wild card を表すことにすると、完全にマッチングしているかはΣa[i]b[i+s](a[i]-b[i+s])^2 が0かどうかで分かる。展開すると全ての項が FFT で計算できる形になっている。

Aさんは順列PをK個に分割する。Bさんはそれらを辞書順最大になるように並べかえる。Aさんは辞書順最小に分割するとき、どのように分割されるか。（ARC114F）

文字列Sの先頭からk文字を取り除いて好きな場所に挿入することで、文字列Tにしたい。kの最小値を線形時間で求めよ(ARC154B)。

前計算O(nlogn)の下、部分文字列の一致判定がO(1)でてきる。これは、長さ2^iのランクがsuffix arrayのアルゴリズムて求まるため。
squareを探すには、長さ2^iの各部分文字列について、それと一致する最近接の部分文字列だけを候補として調べればよいのでO(nlogn)になる。

maximal repetitionは分割統治（Main Lorentz）によりO(nlogn)

3つの隣接する文字\(a_ia_{i+1}a_{i+2}\)について \(a_i \neq a_{i+1},a_{i+1} \neq a_{i+2}\) ならば \(a_{i+1}\) を削除できる。任意の隣接する文字が相異なる文字列\(a_1a_2 \ldots a_n\)について、\(a_1a_n\) にできる必要十分条件は、ある2文字の繰り返しで表せないことである。例えば、\(a(bc)^i=a(cb)^{i-1}c=a(bc)^{i-2}\) のようにできる。

任意の長さ奇数の語は長さ1以下にできる。従って、先頭がBの語および末尾がAの語は空語にできる。A..Bの形の語が空語にできるか考える。AxAByB (x, yは長さ偶数の語）と表せると、AxA, ByB が空語にできる。従って、ABはAが奇数番目になければならない。逆に、そのような語は帰納法により空語にできない（toyota2023spring_final_f）。