結果
問題 | No.430 文字列検索 |
ユーザー | tcltk |
提出日時 | 2023-07-04 02:29:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 371 ms / 2,000 ms |
コード長 | 1,913 bytes |
コンパイル時間 | 320 ms |
コンパイル使用メモリ | 87,080 KB |
実行使用メモリ | 144,060 KB |
最終ジャッジ日時 | 2023-09-25 00:02:08 |
合計ジャッジ時間 | 6,746 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 231 ms
84,144 KB |
testcase_01 | AC | 371 ms
144,060 KB |
testcase_02 | AC | 277 ms
88,184 KB |
testcase_03 | AC | 285 ms
87,928 KB |
testcase_04 | AC | 230 ms
84,068 KB |
testcase_05 | AC | 227 ms
83,684 KB |
testcase_06 | AC | 228 ms
84,036 KB |
testcase_07 | AC | 229 ms
84,112 KB |
testcase_08 | AC | 334 ms
137,600 KB |
testcase_09 | AC | 238 ms
84,736 KB |
testcase_10 | AC | 255 ms
87,592 KB |
testcase_11 | AC | 309 ms
94,768 KB |
testcase_12 | AC | 300 ms
94,448 KB |
testcase_13 | AC | 303 ms
94,424 KB |
testcase_14 | AC | 296 ms
90,972 KB |
testcase_15 | AC | 292 ms
88,992 KB |
testcase_16 | AC | 282 ms
87,800 KB |
testcase_17 | AC | 284 ms
87,708 KB |
ソースコード
#!/usr/bin/env python3 # from typing import * import sys import io import math import collections import decimal import itertools import bisect import heapq import random def input(): return sys.stdin.readline()[:-1] # sys.setrecursionlimit(1000000) # _INPUT = """AAAA # 4 # A # AA # AAA # AAAA # """ # sys.stdin = io.StringIO(_INPUT) INF = 10**10 class RollingHash(): def __init__(self, A, b=3491, m=999999937): n = len(A) self.prefix = [0] * (n+1) self.power = [1] * (n+1) self.b = b self.m = m for i in range(n): self.prefix[i+1] = (self.prefix[i] * b + A[i]) % m self.power[i+1] = (self.power[i] * b) % m def get(self, l, r): # S[l, r) のハッシュ return (self.prefix[r] - self.power[r-l] * self.prefix[l]) % self.m def concat(self, h1, h2, l2): # S1+S2 のハッシュを、それぞれのハッシュから求める return (self.power[l2] * h1 + h2) % self.m def lcp(self, l1, r1, l2, r2): # S[l1, r1) とS[l2, r2) の最大共通接頭辞を求める""" # LCPの最小値 (範囲内) low = 0 # LCPの最大値 + 1 (範囲外) high = min(r1-l1, r2-l2) + 1 while high - low > 1: mid = (high + low) // 2 if self.get(l1, l1 + mid) == self.get(l2, l2 + mid): low = mid else: high = mid return low MOD = 10**9+7 S = [ord(c)-ord('A') for c in input()] M = int(input()) b = random.randint(2, MOD-1) rhash = RollingHash(S, b, MOD) T = [collections.defaultdict(int) for _ in range(10)] for l in range(1, 11): for i in range(len(S)-l+1): T[l-1][rhash.get(i, i+l)] += 1 ans = 0 for _ in range(M): s = [ord(c)-ord('A') for c in input()] rhash_s = RollingHash(s, b, MOD) ans += T[len(s)-1][rhash_s.get(0, len(s))] print(ans)