結果

問題 No.430 文字列検索
コンテスト
ユーザー maizeaux
提出日時 2022-02-09 13:33:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 325 ms / 2,000 ms
コード長 2,463 bytes
コンパイル時間 141 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 118,220 KB
最終ジャッジ日時 2024-11-10 00:59:42
合計ジャッジ時間 4,879 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
from email.policy import default
import sys
import os
from typing import List

sys.setrecursionlimit(100000)
is_local = "TERM_PROGRAM" in os.environ
input = sys.stdin.readline
INF = float('inf')

def debug(*args, **kwargs):
    if is_local:
        print(*args, **kwargs)
def I(): return input().rstrip()
def IS(): return input().split()
def II(): return int(input())
def IIS(): return map(int, input().split())
def LIIS(): return list(map(int, input().split()))

class RollingHash:
    base: int
    base_pow: List[int]
    cum: List[int]
    mod = (1 << 61) - 1
    mask30 = (1 << 30) - 1
    mask31 = (1 << 31) - 1
    positivizer = mod*4
    def __init__(self, base: int):
        self.base = base
        self.base_pow = [1]
        self.cum = [0]

    def calc_cum(self, ls: List[int]):
        for x in ls:
            self.cum.append(self.calc_mod(self.mul(self.cum[-1], self.base) + x))
            self.base_pow.append(self.calc_mod(self.mul(self.base_pow[-1], self.base)))

    def mul(self, x: int, y: int) -> int:
        xu = x >> 31
        xd = x & self.mask31
        yu = y >> 31
        yd = y & self.mask31
        mid = xu * yd + xd * yu
        midu = mid >> 30
        midd = mid & self.mask30
        return xu * yu * 2 + midu + (midd << 31) + xd * yd

    def calc_mod(self, x: int) -> int:
        xu = x >> 61
        xd = x & self.mod
        res = xu + xd
        if res >= self.mod:
            res -= self.mod
        return res

    def hash_range(self, l: int, r: int):
        # [l, r)
        return self.calc_mod(self.cum[r] + self.positivizer - self.mul(self.cum[l], self.base_pow[r-l]))

    def hash(self, ls: List[int]):
        out = 0
        for x in ls:
            out = self.calc_mod(self.mul(out, self.base) + x)
        return out

def main():
    s = I()
    n = len(s)
    import random
    base = random.randint(27, 10000)
    mapping = random.sample(range(1, base), 26)
    def convert(s):
        return [mapping[ord(c)  - ord("A")] for c in s]

    rh = RollingHash(base)
    rh.calc_cum(convert(s))
    cnt = defaultdict(int)
    for i in range(1, 11):
        if i > n:
            break
        for j in range(n-i+1):
            cnt[rh.hash_range(j, j+i)] += 1

    m = II()
    out = 0
    for _ in range(m):
        ss = I()
        h = rh.hash(convert(ss))
        # debug(ss, h, cnt[h])
        out += cnt[h]
    print(out)


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