クマーの競プロ精進日記

AtCoder赤とICPC World Final目指して頑張ります.競プロ自戦記、アルゴリズムなどについて

A+B と B+A がともに回文になるための必要十分条件

未証明だけど多分正しい主張

2 つの文字列 X, Y をこの順で連結したものを  X+Y で表す.文字列  A, B について, a = |A|, b=|B|, g = \gcd(|A|, |B|), a' = a/g, b'=b/g とおく. A+B, B+A がともに回文となるための必要十分条件は以下の通りである:

  • S A の先頭  g 文字を抜き出して得られる文字列とする. S' を文字列  S の反転とする.このとき  A S S' をこの順で繰り返して得られる文字列で, B S' S をこの順で繰り返して得られる文字列である. 例えば  A = S+S'+S+S'+\cdots+S+S' または  A = S+S'+S+S'+\cdots+S'+S である.
  •  a', b' のうち一方が偶数の場合, S は回文である.