結果

問題 No.430 文字列検索
コンテスト
ユーザー maizeaux
提出日時 2022-02-08 20:15:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,297 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 74,496 KB
最終ジャッジ日時 2024-11-10 00:59:39
合計ジャッジ時間 3,627 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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))
    m = II()
    out = 0
    for _ in range(m):
        ss = I()
        ns = len(ss)
        h = rh.hash(convert(ss))
        for i in range(n-ns+1):
            if rh.hash_range(i, i+ns) == h:
                out += 1
    print(out)


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