noshi91のメモ

データ構造のある風景

文字列の連結と辞書順の関係を冪級数で証明

概要

cp-unspoiler

この問題の公式解説にある補題群を冪級数を用いて証明する。

定義

この記事内では以下のように定義する。

\displaystyle \Sigma := \lbrace 1 , 2 , \dots , \sigma \rbrace \\ \displaystyle \Sigma ^ { + } := \Sigma \text{ 上の空でない有限列全体 } \\ \displaystyle \Sigma ^ { \ast } := \Sigma \text{ 上の有限または無限列全体 }

また、列の大小関係を辞書順で定める。

辞書順関連

\varepsilon \gt 0 を十分小さい正の実数とし、 f \colon \Sigma ^ { \ast } \to \mathbb R を \displaystyle f ( S ) := \sum _ { i = 0 } ^ { \infty } S _ i \varepsilon ^ i で定める。

このとき S , T \in \Sigma ^ { \ast } について S \lt T \iff f ( S ) \lt f ( T ) となる。

定理 1 : S , T \in \Sigma ^ { + } について、 S ^ { \infty } \lt T ^ { \infty } \iff S T \lt T S

証明:

\begin{align} & & S ^ { \infty } & \lt T ^ { \infty } \cr & \iff & f ( S ^ { \infty } ) & \lt f ( T ^ { \infty } ) \cr & \iff & \frac { f ( S ) } { 1 - \varepsilon ^ { \lvert S \rvert } } & \lt \frac { f ( T ) } { 1 - \varepsilon ^ { \lvert T \rvert } } \cr & \iff & f ( S ) \left ( 1 - \varepsilon ^ { \lvert T \rvert } \right ) & \lt f ( T ) \left ( 1 - \varepsilon ^ { \lvert S \rvert } \right ) \cr & \iff & f ( S ) + \varepsilon ^ { \lvert S \rvert } f ( T ) & \lt f ( T ) + \varepsilon ^ { \lvert T \rvert } f ( S ) \cr & \iff & f ( S T ) & \lt f ( T S ) \cr & \iff & S T & \lt T S \quad \blacksquare \end{align}

以下の系は、文字列を並び替えてその連結の辞書順を最小化あるいは最大化したい場合に用いる事実として有名である。

系 2 : \Sigma ^ { + } 上の順序 \preceq を S \preceq T \iff S T \leq T S で定めると弱順序となる。

定理 3: S \in \Sigma ^ { + } , T \in \Sigma ^ { \ast } について、 S ^ { \infty } \lt T \iff S T \lt T

証明:

\begin{align} & & S ^ { \infty } & \lt T \cr & \iff & f ( S ^ { \infty } ) & \lt f ( T ) \cr & \iff & \frac { f ( S ) } { 1 - \varepsilon ^ { \lvert S \rvert } } & \lt f ( T ) \cr & \iff & f ( S ) & \lt f ( T ) \left ( 1 - \varepsilon ^ { \lvert S \rvert } \right ) \cr & \iff & f ( S ) + \varepsilon ^ { \lvert S \rvert } f ( T ) & \lt f ( T ) \cr & \iff & f ( S T ) & \lt f ( T ) \cr & \iff & S T & \lt T \quad \blacksquare \end{align}

LCP関連

g \colon \Sigma ^ { \ast } \to \mathbb R \lbrack \lbrack x \rbrack \rbrack を \displaystyle g ( S ) := \sum _ { i = 0 } ^ { \infty } S _ i x ^ i で定める。 また、 s \in \mathbb R \lbrack \lbrack x \rbrack \rbrack について \mathrm { ord } ( s ) := \min \lbrace k \mid \lbrack x ^ k \rbrack s \neq 0 \rbrace とする。

このとき S , T \in \Sigma ^ { \ast } について \mathrm { len } ( \mathrm { LCP } ( S , T ) ) = \mathrm { ord } ( g ( S ) - g ( T ) ) となる。

補題 4 : s , t \in \mathbb R \lbrack \lbrack x \rbrack \rbrack が \lbrack x ^ 0 \rbrack t \neq 0 を満たすなら \mathrm { ord } ( s ) = \mathrm { ord } ( s t )

証明: 何かを乗じることで \mathrm { ord } が減少することはない。仮定より t は乗法逆元を持つので、 \mathrm { ord } ( s ) \leq \mathrm { ord } ( s t ) \leq \mathrm { ord } ( s t t ^ { - 1 } ) = \mathrm { ord } ( s ) 。 \blacksquare

定理 4 : S \in \Sigma ^ { + } , T \in \Sigma ^ { \ast } について、 \mathrm { LCP } ( S ^ { \infty } , T ) = \mathrm { LCP } ( S T , T )

証明:

\begin{align} \mathrm { len } ( \mathrm { LCP } ( S ^ { \infty } , T ) ) & = \mathrm { ord } ( g ( S ^ { \infty } ) - g ( T ) ) \cr & = \mathrm { ord } \left ( \frac { g ( S ) } { 1 - x ^ { \lvert S \rvert } } - g ( T ) \right ) \cr & = \mathrm { ord } \left ( g ( S ) - g ( T ) \left ( 1 - x ^ { \lvert S \rvert } \right ) \right ) \cr & = \mathrm { ord } \left ( \left ( g ( S ) + x ^ { \lvert S \rvert } g ( T ) \right ) - g ( T ) \right ) \cr & = \mathrm { ord } ( g ( S T ) - g ( T ) ) \cr & = \mathrm { len } ( \mathrm { LCP } ( S T , T ) ) \end{align}

LCP の長さが等しく、 T が共通しているから、 \mathrm { LCP } ( S ^ { \infty } , T ) = \mathrm { LCP } ( S T , T ) である。 \blacksquare

定理 5 : S , T \in \Sigma ^ { + } について、 S T \neq T S ならば \mathrm { LCP } ( S ^ { \infty } , T ^ { \infty } ) = \mathrm { LCP } ( S T , T S )

証明:

定理 4 を繰り返し用いて、 \mathrm { LCP } ( S ^ { \infty } , T ^ { \infty } ) = \mathrm { LCP } ( S T ^ { \infty } , T ^ { \infty } ) = \mathrm { LCP } ( S T ^ { \infty } , T S T ^ { \infty } ) 。 S T \neq T S より、 \mathrm { LCP } ( S T ^ { \infty } , T S T ^ { \infty } ) = \mathrm { LCP } ( S T , T S )。 \blacksquare

定理 4 から定理 5 を導いたように、定理 3 から定理 1 を導くこともできる。 定理 5 を直接示そうとすると、LCP の長さが等しいことは分かるが、LCP 自体が等しいことは上手く示せそうにない。

追記

LCP の一致と辞書順の一致から、LCP の次の文字の組み合わせも一致しているのではないかという推測ができ、これは正しい。 文字集合を不定元によって \Sigma := \lbrace x _ 1, x _ 2, \dots, x _ { \sigma } \rbrace と定め、 \mathbb Z \lbrack x _ 1 , x _ 2 , \dots , x _ { \sigma } \rbrack \lbrack \lbrack x \rbrack \rbrack 上で LCP の節と同様の議論を行う。 その際、 \mathrm { ord } だけでなく \lbrack x ^ { \mathrm { ord } ( s ) } \rbrack s も g ( S ^ { \infty } ) - g ( T ) と g ( S T ) - g ( T ) で一致していることが示され、証明を得る。

定理 6: S \in \Sigma ^ { + } , T \in \Sigma ^ { \ast } について、 k := \mathrm { len } ( \mathrm { LCP } ( S ^ { \infty } , T ) ) = \mathrm { len } ( \mathrm { LCP } ( S T , T ) ) とする。 k が有限なら S ^ { \infty } _ k = ( S T ) _ k

定理 7: S , T \in \Sigma ^ { + } について、 k := \mathrm { len } ( \mathrm { LCP } ( S ^ { \infty } , T ^ { \infty } ) ) = \mathrm { len } ( \mathrm { LCP } ( S T , T S ) ) とする。 k が有限なら S ^ { \infty } _ k = ( S T ) _ k かつ T ^ { \infty } _ k = ( T S ) _ k