class StringHash:
    def __init__(self, s=""):
        self.MOD = 998244353
        self.BASE = 131
        # 计算前缀哈希值
        n = len(s)
        P = [0] * (n + 1)
        P[0] = 1
        for i in range(1, n + 1, 1):
            P[i] = P[i - 1] * self.BASE % self.MOD
        H = [0] * (n + 1)
        for i in range(1, n + 1, 1):
            H[i] = (H[i - 1] * self.BASE + ord(s[i - 1])) % self.MOD
        self.H = H
        self.P = P

    '''
    s的[l,r]区间的hash值，闭区间, l从1开始
    '''

    def get_hash(self, l=0, r=0):
        l, r = l + 1, r + 1
        return (self.H[r] - self.H[l - 1] * self.P[r - l + 1] % self.MOD + self.MOD) % self.MOD

示例: https://leetcode.cn/problems/maximum-deletions-on-a-string/submissions/
class Solution:
    def deleteString(self, s: str) -> int:
        n = len(s)
        dp = [1] * n
        hash = StringHash(s)
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if (j - i + 1) % 2 == 0:
                    mid = (i + j) // 2
                    if hash.get_hash(i, mid) == hash.get_hash(mid+1, j):
                        # print(i, j, mid)
                        dp[i] = max(dp[i], dp[mid+1]+1)
                        # print(dp[i])
        # print(dp)
        return dp[0]