結果

問題 No.430 文字列検索
ユーザー maizeauxmaizeaux
提出日時 2022-02-08 20:15:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,297 bytes
コンパイル時間 288 ms
コンパイル使用メモリ 86,844 KB
実行使用メモリ 94,004 KB
最終ジャッジ日時 2023-09-05 20:36:15
合計ジャッジ時間 4,191 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 189 ms
86,100 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
権限があれば一括ダウンロードができます

ソースコード

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