結果
問題 | No.430 文字列検索 |
ユーザー | tcltk |
提出日時 | 2023-07-04 02:29:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 251 ms / 2,000 ms |
コード長 | 1,913 bytes |
コンパイル時間 | 157 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 139,904 KB |
最終ジャッジ日時 | 2024-11-10 01:06:42 |
合計ジャッジ時間 | 4,096 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 126 ms
87,040 KB |
testcase_01 | AC | 251 ms
139,904 KB |
testcase_02 | AC | 174 ms
91,648 KB |
testcase_03 | AC | 186 ms
91,648 KB |
testcase_04 | AC | 138 ms
86,784 KB |
testcase_05 | AC | 135 ms
87,040 KB |
testcase_06 | AC | 126 ms
86,912 KB |
testcase_07 | AC | 125 ms
87,040 KB |
testcase_08 | AC | 227 ms
139,776 KB |
testcase_09 | AC | 136 ms
89,216 KB |
testcase_10 | AC | 149 ms
89,984 KB |
testcase_11 | AC | 193 ms
97,280 KB |
testcase_12 | AC | 191 ms
97,152 KB |
testcase_13 | AC | 192 ms
97,024 KB |
testcase_14 | AC | 189 ms
93,696 KB |
testcase_15 | AC | 185 ms
92,288 KB |
testcase_16 | AC | 179 ms
91,008 KB |
testcase_17 | AC | 181 ms
90,880 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)