結果

問題 No.2204 Palindrome Splitting (No Rearrangement ver.)
ユーザー meruuu61779999
提出日時 2023-02-05 23:45:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,584 ms / 2,000 ms
コード長 4,762 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 156,552 KB
最終ジャッジ日時 2024-07-04 08:58:32
合計ジャッジ時間 31,551 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random

"""ローリングハッシュ

文字列にハッシュをかけて1次元の数に置き換えます。
長い文字列でも、一致判定をO(1)くらいでできます。

・使い方
rh=RollingHash(S): インスタンス作成。 計算量: O(len(S))
rh.value(l,r): 半開区間[l,r)のハッシュ値を返します。 計算量: O(1)
rh.merged_string_value(section_list):
    半開区間をたくさん入れたリストsection_listについて、
    各区間の文字列を連結させてできる文字列のハッシュ値を返します。
    計算量: O(len(section_list)) (そんなにやばくない)
rh.same(section_list1,section_list2):
    2つの文字列が同じならTrueを、そうでないならFalseを返します。
    計算量: O(len(section_list1)+len(section_list2)) (そんなにやばくない)

・使わせてもらったもの
ミラーラビン素数判定法【https://qiita.com/srtk86/items/609737d50c9ef5f5dc59】
"""


def is_prime(n):
    if n == 2:
        return True
    if n == 1 or n & 1 == 0:
        return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1
        if y != n - 1 and t & 1 == 0:
            return False
    return True


# 区間[left,right)内の素数を1つランダムに出力します。
def prime_generator(left, right):
    while True:
        ret_prime = random.randrange(left, right)
        if is_prime(ret_prime):
            return ret_prime


class RollingHashConst:
    hash_dic = dict()
    rhMOD = prime_generator(1 << 32, 1 << 33)
    cf = random.randrange(1 << 22, 1 << 23)
    rui_cf2 = [1]

    def regist_element(self, el):
        rd = random.randrange(1 << 22, 1 << 23)
        self.hash_dic[el] = rd

    def hashed_value(self, el):
        if el not in self.hash_dic:
            self.regist_element(el)
        return self.hash_dic[el]

    def get_rui_cf(self, length):
        if len(self.rui_cf2) < length:
            self.make_rui_cf(length)
        return self.rui_cf2

    def make_rui_cf(self, length):
        need_add_cnt = length - len(self.rui_cf2)
        for _ in range(need_add_cnt):
            new_val = self.rui_cf2[-1] * self.cf % self.rhMOD
            self.rui_cf2.append(new_val)


class RollingHash(RollingHashConst):
    def __init__(self, init_S):
        self.n = len(init_S)
        self.hashed_list = [0]
        val = 0
        for s in init_S:
            val *= self.cf
            val += self.hashed_value(s)
            val %= self.rhMOD
            self.hashed_list.append(val)

        self.rui_cf = self.get_rui_cf(length=self.n + 1)

    def value(self, l, r):
        assert 0 <= l < r <= self.n, f'0<=l<r<=n, {l=}, {r=}'
        retval = self.hashed_list[r]
        retval -= self.hashed_list[l] * self.rui_cf[r - l] % self.rhMOD
        retval %= self.rhMOD
        return retval

    def merged_string_value(self, section_list):
        value_length_list = []
        for l, r in section_list:
            value_length_list.append((self.value(l, r), r - l))
        right_string_length = 0
        retval = 0
        while value_length_list:
            val, length = value_length_list.pop()
            val *= self.rui_cf[right_string_length]
            val %= self.rhMOD
            right_string_length += length
            retval += val
            retval %= self.rhMOD
        return retval

    def section_length(self, section_list):
        ret_length = 0
        for l, r in section_list:
            ret_length += r - l
        return ret_length

    def same(self, section_list1, section_list2):
        if self.section_length(section_list1) != self.section_length(
                section_list2):
            return False
        if self.merged_string_value(section_list1) != self.merged_string_value(
                section_list2):
            return False
        return True


def main():
    S = input()

    N = len(S)
    S_rev = S[::-1]
    rh = RollingHash(S)
    rh_rev = RollingHash(S_rev)

    def is_palindrome(l, r):
        return rh.value(l, r) == rh_rev.value(N - r, N - l)

    G = [[] for _ in range(N + 1)]
    for i in range(N):
        for j in range(i + 1, N + 1):
            if is_palindrome(i, j):
                G[i].append(j)

    score = [0] * (N + 1)
    score[0] = 1 << 30
    for i in range(N):
        before_score = score[i]
        for ni in G[i]:
            length = ni - i
            new_score = min(length, before_score)
            score[ni] = max(score[ni], new_score)
    print(score[-1])


if __name__ == "__main__":
    main()
0