ABC284-F ABCBAC (Python)

問題

解き方

ローリングハッシュ。
クラス化したものを自分で持っとくとラクそう。あとでやろ。
ローリングハッシュの説明自体は、他の記事だったり本だったりにおまかせします。

具体的な方法

入力例1の「abcbac」でやってみます。
最初は、左半分の「abc」と、右半分を反転させた「cab」が一致してるかどうかを見る。
ここからローリングします。i(1≦i≦N)回目の操作では、
・左半分の「abc」→ 右からi番目の文字を消す「ab」→さっき消した位置に今度は元の文字列の右からi番目の文字を挿入する「abc」
・右半分を反転させた「cab」→ 先頭の文字を消す「ab」→末尾に元の文字列のN-i+1文字目を挿入する「abc」
のように文字列を動かして、同じかどうか判定します。
細かいことはコードを見てください。

ACコード

import random

N = int(input())
T = input()

# hash_dic[(英小文字)] = 乱数
hash_dic = dict()
for i in range(26):
    alp = chr(97 + i)  # chr(97)='a'だよ
    rd = random.randint(1, 2 ** 60)
    hash_dic[alp] = rd

a = random.randint(2, 2 ** 60)
mod = random.randint(2 ** 63, 2 ** 64)

# rui_a[i]: a^iをmodで割ったあまり
rui_a = []
num = 1
for _ in range(N):
    rui_a.append(num)
    num = num * a % mod

# 最初は、文字列Tがf_N(S)かどうかの確認をしてみる。
# ということで、文字列Tの左半分をローリングハッシュ
val_base = 0
for i in range(N):
    t = T[i]
    val_base += rui_a[N - 1 - i] * hash_dic[t] % mod
    val_base %= mod

# 文字列Tの右半分を「反転させたもの」をローリングハッシュ
val_rev = 0
for i in range(N):
    t = T[2 * N - 1 - i]
    val_rev += rui_a[N - 1 - i] * hash_dic[t] % mod
    val_rev %= mod

# 入力例3みたいなパターンだけ先に個別で処理しとく。
if val_base == val_rev:
    print(T[:N])
    print(N)
    exit()

for i in range(N):
    # val_baseは、末尾のT[N-1-i]を取り除いて、末尾にT[2*N-1-i]をつけ加える。
    val_base -= rui_a[i] * hash_dic[T[N - 1 - i]] % mod
    val_base += rui_a[i] * hash_dic[T[2 * N - 1 - i]] % mod
    val_base %= mod

    # val_revは、(右側を先頭として)先頭のT[2*N-1-i]を取り除いて、末尾にT[N-1-i]をつけ加える。
    val_rev -= rui_a[N - 1] * hash_dic[T[2 * N - 1 - i]] % mod
    val_rev %= mod
    val_rev *= a  # 文字列の先頭の位置が1つ左にずれてるから、各項の係数をそれぞれa倍してあげる。
    val_rev += rui_a[0] * hash_dic[T[N - 1 - i]] % mod
    val_rev %= mod

    if val_base == val_rev:
        print(T[:N - 1 - i] + T[2 * N - 1 - i:])
        print(N - 1 - i)
        exit()

print(-1)