ABC468Dを解いた【回文探索】

筆者はレート800前後の茶～緑コーダ

ABC468のD問題を解いていく

実装コード

各位置を奇数長・偶数長の中心として左右に広げ、不一致が1組以下の部分文字列を数える。

• 文字列 S を受け取り、長さを N とする
• k = 0 では奇数長、k = 1 では偶数長の部分文字列を調べる
• 各位置 t に対して、左右の位置を l = t - k、r = t として中心から探索を始める
• l と r が文字列の範囲内にある間、S[l] と S[r] を比較する
• 左右の文字が異なるたびに不一致数 c を増やし、2組目の不一致が見つかったら探索を打ち切る
• 不一致が1組以下なら ans を1増やし、l を左、r を右へ動かしてさらに広げる
• すべての中心について数え終えたら ans を出力する

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    S = rS()
    N = len(S)
    ans = 0
    for k in range(2):
        for t in range(N):
            l, r = t - k, t
            c = 0
            while 0 <= l and r < N:
                if S[l] != S[r]:
                    c += 1
                    if c == 2:
                        break
                l -= 1
                r += 1
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

感想

奇数長と偶数長を k でまとめて中心から探索する実装が勉強になった。
不一致の組数を数えながら広げると、2組目が出た時点でそれ以上外側は調べなくてよいので、「ほぼ回文」の数え上げを簡潔に書けると感じた。