問題リンク: A - ST and TS Palindrome
私「これ SS' and S'S Palindrome では？」
chokudai さん「うるへぇ」
無限文字列 $U$ の定義
左右に無限に続く文字列 $U = \cdots STSTSTST \cdots$ を考えるとよいです。
文字のインデックスは、ある $S$ の先頭が $0$ であるように定義しておきます。
$U$ の条件の言い換え
このとき $U$ の満たすべき条件は以下です。
$$ \begin{cases} U_i = U_j & (i + j = N + K - 1), \\ U_i = U_j & (i + j = N - K - 1), \\ U_i = U_j & (i + N + K = j) \end{cases} $$
この条件は $\mathbb{Z}$ への次の $3$ つの作用の生成する群 $G$ で不変であると言い換えられます。
$$ \begin{cases} i \mapsto N + K - 1 - i, \\ i \mapsto N - K - 1 - i, \\ i \mapsto i + N + K \end{cases} $$
$g = \mathrm{gcd}(N + K, 2K)$ と定めると、群 $G$ は次のもので生成されます。
$$ \begin{cases} i \mapsto i + g, \\ i \mapsto g - 1 - i \end{cases} $$
従って $U$ に関する条件は、$S$ の始点から始まる長さ $g$ の回文の繰り返しになっていることであることがわかります。
$S$ の条件への言い換え
$N \le g$ のときは、$S _ {N - g}, \dots, S _ {N - 1}$ が回文であることと同値です。
$N \ge g$ のときは、$S$ が周期 $g$ を持ち、$S _ 0, \dots, S _ { g - 1 }$ が回文であること同値です。
