結果

問題 No.430 文字列検索
ユーザー maizeauxmaizeaux
提出日時 2022-02-09 13:33:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 589 ms / 2,000 ms
コード長 2,463 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 87,224 KB
実行使用メモリ 141,572 KB
最終ジャッジ日時 2023-09-06 17:54:42
合計ジャッジ時間 10,007 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 339 ms
98,588 KB
testcase_01 AC 589 ms
141,572 KB
testcase_02 AC 458 ms
107,948 KB
testcase_03 AC 483 ms
107,640 KB
testcase_04 AC 360 ms
98,556 KB
testcase_05 AC 377 ms
98,696 KB
testcase_06 AC 376 ms
98,392 KB
testcase_07 AC 363 ms
98,360 KB
testcase_08 AC 538 ms
141,468 KB
testcase_09 AC 345 ms
98,968 KB
testcase_10 AC 378 ms
106,016 KB
testcase_11 AC 485 ms
111,268 KB
testcase_12 AC 521 ms
111,016 KB
testcase_13 AC 486 ms
111,048 KB
testcase_14 AC 474 ms
107,860 KB
testcase_15 AC 472 ms
107,600 KB
testcase_16 AC 465 ms
107,804 KB
testcase_17 AC 460 ms
107,788 KB
権限があれば一括ダウンロードができます

ソースコード

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