ABC468 D - Pre-Palindrome
準回文
考え方
可能性がある $L,R$ の組は、最大で $N(N+1)/2$ 個。
つまり、$1$ つの候補を $O(1)$ で調べられるなら、全探索で間に合う。
例えば、「$3$ 文字目から $9$ 文字目は準回文か？」という問いには、以下で答えられる。
- $4$ 文字目から $8$ 文字目が完全回文、かつ $3$ 文字目と $9$ 文字目が一致なら、完全回文
- $4$ 文字目から $8$ 文字目が完全回文、かつ $3$ 文字目と $9$ 文字目が不一致なら、準回文
- $4$ 文字目から $8$ 文字目が準回文、かつ $3$ 文字目と $9$ 文字目が一致なら、準回文
つまり、普通の回文判定と同じようにしながら、不一致 $1$ 回までならセーフという感じでやればよいだけ。
計算量は $O(N^2)$。
入力例1での動作
入力を受け取る。
s: "ababa"
n: 5個数を数える変数 result を $0$ で初期化する。
result: 0まず d=0 とし、奇数長の部分文字列を調べる。
このとき、i が部分文字列の中心になる。
$i=0$ のとき、最初は $j=0$ である。
s[0] と s[0] は等しいので、counter は $0$ のままである。
条件を満たす部分文字列 "a" を数え、result に $1$ 加える。
result: 1$i=1$ のとき、まず $j=0$ で s[1] と s[1] を比較する。
等しいので、部分文字列 "b" を数える。
次に $j=1$ で s[0] と s[2] を比較する。
どちらも a なので、部分文字列 "aba" も数える。
result: 3$i=2$ のとき、中心から順に、
- $j=0$ で
s[2]とs[2] - $j=1$ で
s[1]とs[3] - $j=2$ で
s[0]とs[4]
を比較する。
どの組も等しいので、部分文字列 "a"、"bab"、"ababa" を数える。
result: 6$i=3$ のとき、部分文字列 "b" と "aba" を数える。
result: 8$i=4$ のとき、部分文字列 "a" を数える。
result: 9次に d=1 とし、偶数長の部分文字列を調べる。
このとき、i と i+1 の間が部分文字列の中心になる。
$i=0$ のとき、$j=0$ で s[0] と s[1] を比較する。
a と b で異なるので、counter に $1$ 加える。
counter は $1$ 以下なので、$1$ 文字の書き換えで回文にできる部分文字列 "ab" を数える。
result: 10$i=1$ のとき、まず $j=0$ で s[1] と s[2] を比較する。
b と a で異なるので、counter は $1$ となる。
部分文字列 "ba" は条件を満たすので数える。
次に $j=1$ で s[0] と s[3] を比較する。
a と b で異なるので、counter は $2$ となる。
部分文字列 "abab" は $1$ 文字の書き換えでは回文にできないため数えない。
counter>1 となった時点で、この中心についての調査を終了する。
result: 11$i=2$ のとき、$j=0$ で s[2] と s[3] を比較する。
a と b で異なるので、部分文字列 "ab" を数える。
次に $j=1$ で s[1] と s[4] を比較する。
b と a で異なり、counter が $2$ となる。
部分文字列 "baba" は数えず、この中心についての調査を終了する。
result: 12$i=3$ のとき、$j=0$ で s[3] と s[4] を比較する。
b と a で異なるので、部分文字列 "ba" を数える。
result: 13$i=4$ のときは、右側の添字 i+j+d が最初から $n$ 以上になるため、調べる部分文字列はない。
注意点
特になし。
別解
特になし。