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まず、奇数長の部分文字列を中心から外側へ広げて調べる。
この入力では、どの比較でも左右の文字が一致する。
| 中心 | 数える部分文字列 |
|---|---|
| $0$ | "a" |
| $1$ | "b", "aba" |
| $2$ | "a", "bab", "ababa" |
| $3$ | "b", "aba" |
| $4$ | "a" |
奇数長では $9$ 個を数える。
次に、偶数長の部分文字列を調べる。
左右の不一致が $1$ 組までなら数え、$2$ 組になった時点でその中心についての調査を終了する。
| 中心 | 外側へ広げたときの比較 | 数える部分文字列 |
|---|---|---|
| $0$ と $1$ の間 | a != b |
"ab" |
| $1$ と $2$ の間 | b != a, a != b で不一致が $2$ 組になる |
"ba" |
| $2$ と $3$ の間 | a != b, b != a で不一致が $2$ 組になる |
"ab" |
| $3$ と $4$ の間 | b != a |
"ba" |
偶数長では $4$ 個を数える。
したがって、条件を満たす部分文字列は全部で $9+4=13$ 個となる。
注意点
特になし。
別解
特になし。