回文 | Notion

長さ $N$ の文字列 $S$ について考える。

$S$ を逆から見た文字列を $T$ とする。

$S$ と $T$ が一致したら回文である。

std::string t = s;
std::ranges::reverse(t);
if (s == t) {
	//process
}

例題

k桁の回文について考える。

回文の性質より先頭を決めれば必然的に一番最後の文字も決定される。

つまり

先頭からi桁目を決定すればk-i+1桁目も自動的に決定される。

以上より回文を作るときは前半分だけ作れば残り半分も作れたことになる。

k桁の回文において先頭から$\frac{k+1}{2}$ 桁まで確定すれば残り半分も確定する。 (1-indexed)