ローリングハッシュ
リファレンス
code: RollingHash.py
from random import randint
Hmod = 88875394043211781
base = randint(2, Hmod-2)
def rolling_hash(S):
"""
文字列Sのハッシュテーブルを構築
"""
N = len(S)
while len(memo_pow) < N:
memo_pow.append(memo_pow-1 * base % Hmod) for i in range(N):
Ti+1 += ord(Si) # Sが文字列でないならここを変更 return T
def get_hash(RH, L, R):
"""
RH := ハッシュテーブル
"""
ret = RHR - RHL * memo_powR-L return ret % Hmod