#1186674 (PyPy3) No.2858 Make a Palindrome

• 問題: No.2858 Make a Palindrome
• ユーザー: LyricalMaestro
• 提出日時: 2026-09-13 04:23:22
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: AC
• 実行時間: 268 ms / 3,000 ms
• コード長: 6,325 bytes
• コンパイル時間: 65 ms
• コンパイル使用メモリ: 83,652 KB
• 実行使用メモリ: 98,928 KB
• 最終ジャッジ日時: 2026-09-13 04:23:34
• 合計ジャッジ時間: 9,498 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
other	AC * 40

ソースコード

# https://yukicoder.me/problems/no/2858

H = 9007199254740997
B = 30

# Manacherアルゴリズムの実装
# https://klee.hatenablog.jp/entry/2020/06/18/210754 を参考にした
# 線形時間で回文部分文字列の個数を列挙するアルゴリズム

from typing import List

class ManacherResult:

    def __init__(self, rad_odd_length: List[int], rad_even_length: List[int]):
        self._rad_odd_length = rad_odd_length
        self._rad_even_length = rad_even_length

    def get_max_palindrome_length(self):
        # 奇数長の最大長は 2r - 1, 偶数長の最大長は 2r
        max_odd_rad = max(self._rad_odd_length, default=0)
        max_even_rad = max(self._rad_even_length, default=0)
        odd_len = 2 * max_odd_rad - 1 if max_odd_rad > 0 else 0
        even_len = 2 * max_even_rad
        return max(odd_len, even_len)

    def get_palindrome_count(self):
        return sum(self._rad_odd_length) + sum(self._rad_even_length)


class Manacher:
    """Manacherアルゴリズム

    Aの間と両端に区切り文字を挟んだ列に対して奇数長Manacherを適用することで、
    奇数長・偶数長両方の回文の半径を線形時間で求める。
    """

    def __init__(self, seperator = "#"):
        self._seperator = seperator

    def solve(self, A) -> ManacherResult:
        # 奇数長回文の計算
        rad_odd_length = self._manacher_odd_length(A)

        # 偶数長回文の計算:
        n = len(A)
        # Aの間と両端に区切り文字を挟んだ列 (長さ 2n + 1) を作る
        # B[2i] が区切り、B[2i + 1] が A[i] に対応する
        B = [self._seperator] * (2 * n + 1)
        for i in range(n):
            B[2 * i + 1] = A[i]

        rad = self._manacher_odd_length(B)

        # B[2c] (区切り位置) を中心とする回文が Aでの偶数長回文に対応する。
        # B上の半径 r (区切り位置では常に奇数) は A に射影すると r - 1 文字 (偶数) になる
        # ので、Aでの半径は (r - 1) // 2
        rad_even_length = [(rad[2 * c] - 1) // 2 for c in range(n + 1)]

        return ManacherResult(rad_odd_length, rad_even_length)

    @staticmethod
    def _manacher_odd_length(A) -> List[int]:
        n = len(A)

        rad = [0] * n
        # (c - r, c + r)という開区間
        c = 0
        r = 0
        while c < n:

            # どんどん右に伸ばしていく
            while 0 <= c - r and c + r < n and A[c - r] == A[c + r]:
                r += 1
            rad[c] = r

            # c ~ c + rないについてc - r までの結果を使い回す
            k = 1
            while 0 <= c - k and k + rad[c - k] < r:
                rad[c + k] = rad[c - k]
                k += 1

            # 計算が終わった分だけ前進する
            c += k
            r -= k

        return rad


def solve(N, M, S):
    pow_b_list = [0] * (N + 1)
    pow_b =1
    for i in range(N + 1):
        pow_b_list[i] = pow_b
        pow_b *= B
        pow_b %= H

    # ローリングハッシュ
    if M < N:
        manacher = Manacher()
        result1 = manacher.solve(S)
        if result1.get_max_palindrome_length() >= M:
            return 1

        result2 = manacher.solve(S + S)
        if result2.get_max_palindrome_length() >= M:
            return 2

        return -1
    else:
        forward_hash = [0] * N
        hash0 = 0
        for i in range(N):
            hash0 *= B
            hash0 %= H
            hash0 += ord(S[i % N]) - ord("a") + 1
            hash0 %= H
            forward_hash[i] = hash0

        backward_hash = [0] * (N)
        hash0 = 0
        for i in reversed(range(N)):
            hash0 *= B
            hash0 %= H
            hash0 += ord(S[i % N]) - ord("a") + 1
            hash0 %= H
            backward_hash[i] = hash0

        def is_palindrome(word, left, right):
            n = right - left  + 1
            if n % 2 == 0:
                m = (left + right) // 2
                length = n // 2
                if left > 0:    
                    y = (forward_hash[left - 1] * pow_b_list[length]) % H
                    l = (forward_hash[m] - y) % H
                else:
                    l = forward_hash[m]
                if right < len(word) - 1:
                    y = (backward_hash[right + 1] * pow_b_list[length]) % H
                    r = (backward_hash[m + 1] - y ) % H
                else:
                    r = (backward_hash[m + 1])
                if r == l:
                    return True
                else:
                    return False
            else:
                m = (left + right) // 2
                length = n // 2 + 1
                if left > 0:    
                    y = (forward_hash[left - 1] * pow_b_list[length]) % H
                    l = (forward_hash[m] - y) % H
                else:
                    l = forward_hash[m]
                if right < len(word) - 1:
                    y = (backward_hash[right + 1] * pow_b_list[length]) % H
                    r = (backward_hash[m] - y ) % H
                else:
                    r = (backward_hash[m])
                if r == l:
                    return True
                else:
                    return False

        answer = float("inf")
        # そもそもこの文字全体が回文か
        if is_palindrome(S, 0, len(S) - 1):
            ans = M // len(S) + (1 if M % len(S) > 0 else 0)
            answer = min(answer, ans)

        for mid_right in range(len(S) - 1):
            p1 = is_palindrome(S, 0, mid_right)
            p2 = is_palindrome(S, mid_right + 1, len(S) - 1)
            if p1 and p2:
                max_x = max(mid_right + 1, len(S) - 1 - mid_right)

                ans = M // len(S)
                if ans * len(S) + max_x >= M:
                    answer = min(answer, ans + 1)
                else:
                    answer = min(answer, ans + 2)

        if answer == float("inf"):
            return -1
        else:
            return answer


def main():
    T  = int(input())
    answers = []
    for _ in range(T):
        N, M = map(int ,input().split())
        S = input()
        ans = solve(N, M, S)
        answers.append(ans)

    for ans in answers:
        print(ans)






if __name__ == "__main__":
    main()