結果
問題 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 123 ms
81,948 KB |
testcase_01 | AC | 325 ms
118,220 KB |
testcase_02 | AC | 224 ms
87,832 KB |
testcase_03 | AC | 234 ms
87,488 KB |
testcase_04 | AC | 122 ms
81,496 KB |
testcase_05 | AC | 124 ms
81,772 KB |
testcase_06 | AC | 118 ms
81,792 KB |
testcase_07 | AC | 119 ms
81,612 KB |
testcase_08 | AC | 306 ms
118,064 KB |
testcase_09 | AC | 124 ms
81,736 KB |
testcase_10 | AC | 153 ms
86,784 KB |
testcase_11 | AC | 257 ms
91,680 KB |
testcase_12 | AC | 258 ms
91,776 KB |
testcase_13 | AC | 261 ms
92,000 KB |
testcase_14 | AC | 246 ms
88,372 KB |
testcase_15 | AC | 246 ms
87,572 KB |
testcase_16 | AC | 239 ms
87,808 KB |
testcase_17 | AC | 232 ms
87,452 KB |
ソースコード
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()