ほとんどのケースでは \(f(S,T,X), f(S,T,Y)\) の長さが等しいことから \(T\) の長さがわかる。 \(S,T\) の長さが決まっているときに \(f(S,T,X)=f(S,T,Y)\) が成り立つのは \(S,T\) がどんなときか考えてみる。

具体例

例えば \(|S|=6, |T|=4\) のときに \(S+T+T+S+T+S=T+T+T+S+T+T+T\) が成り立つのはどんなときか考える。先頭を比較するとまず \(T\) が \(S\) の接頭辞で \(|S'|=2\) なる \(S'\) を用いて \(S=T+S'\) と表せることが必要。この置き換えで式は

\(T+S'+T+T+T+S'+T+T+S' = T+T+T+T+S'+T+T+T\)

\(\iff S'+T+T+T+S'+T+T+S' = T+T+T+S'+T+T+T\)

となる。すると今度は \(S'\) が \(T\) の接頭辞となり、 \(|T'|=2\) なる \(T'\) を用いて \(T=S'+T'\) と合わせることが必要。この置き換えで式は

\(S'+ (\) \(S',T'\) の式 \() = T' + (\) \(S',T'\) の式 \()\)

となる。この式では \(|S'|,|T'|\) が等しいので \(S'=T'\) が必要十分である。 \(S'=T'=U\) として \(S,T\) を \(U\) で表すと \(S=U+U+U, T=U+U\) と表せる。逆に \(S,T\) がこのように表せる場合、 \(S,T\) の結合は \(U\) の繰り返しになるので、等式は明らかに成り立つ。よって

• \(|S|=6, |T|=4\) かつ \(S+T+T+S+T+S=T+T+T+S+T+T+T\) \(\iff\) \(S,T\) が長さ \(2\) の文字列 \(U\) を用いて \(S=U+U+U, T=U+U\) と表せる

がわかる。

考察

以上の計算過程を普遍的にとらえてみると

• 等式が \(A+A+B=A+A+B\) という自明な形の場合、どのような \(A,B\) に対しても成立する
• そうでない場合で、式に用いられている\(2\) 種類の文字列 \(A,B\) の長さが異なるとき（ \(|A| < |B|\) とする）、等式は \(A+(\dots)=B+(\dots)\) という形になり、\(B=A+B'\) と表せるのが必要で、 \(A,B'\) に関する同じ形式の問題に帰着される。
• 式に用いられている \(2\) 種類の文字列 \(A,B\) の長さが等しい場合、 \(A=B\) が必要十分

ということが分かり、特に \(2\) 番目の帰着が繰り返され最終的に \(1,3\) 番目の状態に行きつくことが分かる。

帰着の繰り返しにより最終的にどのような状態に行くかを考えたいが、 \(2\) 番目の帰着の際、

• \(A+A+(\dots) = B+(\dots) \iff A + A + (\dots) = A + B' + (\dots) \iff A + (\dots) = B' + (\dots)\)
• \(A+B+(\dots) = B+(\dots) \iff A + A + B'+ (\dots) = A + B' + (\dots) \iff A + B' + (\dots) = B' + (\dots)\)

という帰着が行われるため、等式がはじめ自明な等式でなければ \(2\) 番目の帰着で自明な等式に帰着されることはなく、必ず \(3\) 番目の状態になることがわかる。

\(3\) 番目の状態から \(B=A+B'\) などの置き換えを逆にたどっていくと、結局 \(3\) 番目の状態での \(2\) つの文字列の長さを \(L\) として、 \(A,B\) が長さ \(L\) の共通の文字列 \(C\) の繰り返しになっていることが必要十分だとわかる。

以上より \(L\) さえ求まれば条件判定が簡単にできる。 \(2\) 番目の帰着での長さの変化を考えると \((n,m)\rightarrow (n,m-n)\) という変化を \(n=m\) になるまで繰り返すと考えられる。これはユークリッドの互除法そのものであるため \(L=\mathrm{gcd}(n,m)\) であることが分かる。

解法

まず \(X,Y\) における 1 の個数が等しい場合について考えます。 0 の個数が等しい場合、 \(T=S\) とすれば \(f(S,T,X)=f(S,T,Y)\) が明らかに成り立つので、 答えは Yes です。そうでない場合、 \(f(S,T,X),f(S,T,Y)\) の長さは等しく成りえないので答えは No です。

\(X,Y\) における 1 の個数が等しくない場合、 \(X\neq Y\) であり、 \(|f(S,T,X)|=|f(S,T,Y)|\) から \(|T|\) に関する一次方程式が得られるため、 \(|T|\) が求まります（これが整数にならなかったり、負の値になる場合は No です）。

上記の考察から \(X\neq Y\) のとき、

★ \(f(S,T,X)=f(S,T,Y) \iff S,T\) は長さ \(\mathrm{gcd}(|S|,|T|)\) の文字列 \(U\) の繰り返しである

が成り立ちます。よって条件を満たす \(T\) が存在するのは、 \(S\) が \(\mathrm{gcd}(|S|,|T|)\) を周期として持つときです。これは \(S\) の \(i\) 文字目と \(i+\mathrm{gcd}(|S|,|T|)\) 文字目が等しいか見ればよく、 \(O(|S|)\) 時間でチェックできます。

★のformalな証明

\(||S|-|T||\) に関する帰納法で示す。 \(|S|=|T|\) であるときは明らかである。

\(|S| < |T|\) であるとして一般性を失わない。また、 \(X \neq Y\) であるため、適宜共通する接頭辞を取り除くことで \(X,Y\) の \(1\) 文字目がそれぞれ 0,1 であるとしてよい。すると \(S\) は \(T\) の接頭辞であることが必要で、 \(T=S+T'\) なる \(T'\) が存在することが必要である。すると等式が成り立つには \(X,Y\) それぞれについて、 1 を 01 で同時に置き換えて得られる文字列を \(X',Y'\) とすると \(f(S,T',X')=f(S,T',Y')\) が必要である。 \(X',Y'\) については \(X\) の \(2\) 文字目で場合分けすると \(X' \neq Y'\) が成り立つことが分かり、帰納法の仮定から \(S,T'\) が長さ \(\mathrm{gcd}(|S|,|T|-|S|)=\mathrm{gcd}(|S|,|T|)\) の文字列 \(U\) の繰り返しであることが必要である。これと \(T=S+T'\) を合わせると、 \(T\) も \(U\) の繰り返しになっていることがわかる。以上より必要性が示せた。十分性については明らかである。