Day 015-Q5 — ローリングハッシュ高度応用

問題

文字列 S に対し: palindrome l r は回文判定、lcp l1 l2 len は最長共通接頭辞長。さらに S の最長回文部分文字列を出力。

制約

入出力例

7 2
abacaba
palindrome 1 7
lcp 1 3 4

Yes
3
abacaba

ヒント (段階的開示)

模範解答 (Python)

📋 コピーimport sys
input = sys.stdin.readline

MOD = (1 << 61) - 1
BASE = 131

def build_hash(s):
    n = len(s)
    h = [0] * (n + 1)
    pw = [1] * (n + 1)
    for i, c in enumerate(s):
        h[i+1] = (h[i] * BASE + ord(c)) % MOD
        pw[i+1] = pw[i] * BASE % MOD
    return h, pw

def get_hash(h, pw, l, r):
    return (h[r+1] - h[l] * pw[r-l+1]) % MOD

def manacher(s):
    n = len(s)
    r = [0] * n
    c = right = 0
    for i in range(n):
        if i < right:
            r[i] = min(right - i, r[2*c - i])
        while i - r[i] - 1 >= 0 and i + r[i] + 1 < n and s[i-r[i]-1] == s[i+r[i]+1]:
            r[i] += 1
        if i + r[i] > right:
            c, right = i, i + r[i]
    return r

def main():
    N, Q = map(int, input().split())
    S = input().strip()
    RS = S[::-1]
    h, pw = build_hash(S)
    rh, rpw = build_hash(RS)

    def is_palindrome(l, r):
        l -= 1; r -= 1
        fwd = get_hash(h, pw, l, r)
        rev = get_hash(rh, rpw, N-1-r, N-1-l)
        return fwd == rev

    def lcp_len(l1, l2, length):
        l1 -= 1; l2 -= 1
        lo, hi = 0, length
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if get_hash(h, pw, l1, l1+mid-1) == get_hash(h, pw, l2, l2+mid-1):
                lo = mid
            else:
                hi = mid - 1
        return lo

    results = []
    for _ in range(Q):
        q = input().split()
        if q[0] == 'palindrome':
            l, r = int(q[1]), int(q[2])
            results.append('Yes' if is_palindrome(l, r) else 'No')
        else:
            l1, l2, length = int(q[1]), int(q[2]), int(q[3])
            results.append(lcp_len(l1, l2, length))

    t = '#' + '#'.join(S) + '#'
    r = manacher(t)
    best = max(range(len(t)), key=lambda i: r[i])
    center = best
    radius = r[best]
    s_l = (center - radius) // 2
    s_r = (center + radius) // 2
    print('\n'.join(map(str, results)))
    print(S[s_l:s_r])

main()

Step-by-Step 解説

よくあるミス

次のステップ

• Eertree（Palindromic Tree）で全 palindrome 部分列挙

自己評価

自分の回答

気づき・メモ