結果

問題 No.430 文字列検索
ユーザー proriboneproribone
提出日時 2020-08-11 17:55:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 280 ms / 2,000 ms
コード長 834 bytes
コンパイル時間 137 ms
コンパイル使用メモリ 82,568 KB
実行使用メモリ 107,924 KB
最終ジャッジ日時 2024-04-17 17:28:00
合計ジャッジ時間 2,258 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
55,988 KB
testcase_01 AC 280 ms
107,924 KB
testcase_02 AC 89 ms
80,132 KB
testcase_03 AC 93 ms
80,468 KB
testcase_04 AC 38 ms
56,164 KB
testcase_05 AC 37 ms
56,900 KB
testcase_06 AC 37 ms
56,452 KB
testcase_07 AC 36 ms
56,168 KB
testcase_08 AC 68 ms
84,304 KB
testcase_09 AC 44 ms
63,464 KB
testcase_10 AC 63 ms
77,060 KB
testcase_11 AC 126 ms
85,968 KB
testcase_12 AC 99 ms
85,056 KB
testcase_13 AC 100 ms
85,124 KB
testcase_14 AC 98 ms
82,764 KB
testcase_15 AC 103 ms
80,892 KB
testcase_16 AC 90 ms
80,300 KB
testcase_17 AC 89 ms
80,320 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random
from collections import Counter
MOD=2**61-1
base=random.randrange(100,MOD)

def RollingHash(S,l):
    arr=[]
    if len(S)<l:
        return arr
    H=0
    b=1
    for i in reversed(range(l)):
        H=(H+(ord(S[i])-65)*b)%MOD
        b=b*base%MOD
    arr.append(H)
    for i in range(l,len(S)):
        H=(H*base-(ord(S[i-l])-65)*pow(base,l,MOD)+(ord(S[i])-65))%MOD
        arr.append(H)
    return arr
    
def Hash(S):
    H=0
    b=1
    for i in reversed(range(len(S))):
        H=(H+(ord(S[i])-65)*b)%MOD
        b=b*base%MOD
    return H

S=input()
M=int(input())
li=[[] for i in range(11)]
for i in range(M):
    C=input()
    li[len(C)].append(C)

ans=0
for i in range(11):
    if not li[i]:
        continue
    Count=Counter(RollingHash(S,i))
    for s in li[i]:
        ans+=Count.get(Hash(s),0)
print(ans)
0