結果
問題 | No.430 文字列検索 |
ユーザー | るこーそー |
提出日時 | 2024-08-16 10:01:33 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 641 ms / 2,000 ms |
コード長 | 805 bytes |
コンパイル時間 | 111 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 58,228 KB |
最終ジャッジ日時 | 2024-11-10 01:12:19 |
合計ジャッジ時間 | 6,420 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 28 ms
10,624 KB |
testcase_01 | AC | 641 ms
58,068 KB |
testcase_02 | AC | 451 ms
16,000 KB |
testcase_03 | AC | 471 ms
15,872 KB |
testcase_04 | AC | 26 ms
10,752 KB |
testcase_05 | AC | 26 ms
10,624 KB |
testcase_06 | AC | 26 ms
10,624 KB |
testcase_07 | AC | 26 ms
10,752 KB |
testcase_08 | AC | 583 ms
58,228 KB |
testcase_09 | AC | 28 ms
10,752 KB |
testcase_10 | AC | 75 ms
13,744 KB |
testcase_11 | AC | 483 ms
20,736 KB |
testcase_12 | AC | 489 ms
20,816 KB |
testcase_13 | AC | 491 ms
20,856 KB |
testcase_14 | AC | 483 ms
18,304 KB |
testcase_15 | AC | 491 ms
18,156 KB |
testcase_16 | AC | 466 ms
16,256 KB |
testcase_17 | AC | 457 ms
16,000 KB |
ソースコード
from collections import defaultdict class RollingHash: def __init__(self,S,base=256,mod=(1<<61)-1): self.MOD=mod self.base=base self.length=len(S) self.hash=[0]*(self.length+1) self.power=[1]*(self.length+1) for i in range(self.length): self.hash[i+1]=(self.hash[i]*self.base+ord(S[i]))%self.MOD self.power[i+1]=(self.power[i]*self.base)%self.MOD def get(self,l,r): return (self.hash[r]-self.hash[l]*self.power[r-l])%self.MOD S=input() rhs=RollingHash(S) dd=defaultdict(int) for length in range(1,11): for i in range(len(S)-length+1): dd[rhs.get(i,i+length)]+=1 m=int(input()) ans=0 for _ in range(m): C=input() rhc=RollingHash(C) ans+=dd[rhc.get(0,len(C))] print(ans)