結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
55,680 KB
testcase_01 AC 271 ms
107,212 KB
testcase_02 AC 91 ms
80,000 KB
testcase_03 AC 98 ms
80,640 KB
testcase_04 AC 38 ms
55,168 KB
testcase_05 AC 41 ms
55,296 KB
testcase_06 AC 39 ms
55,424 KB
testcase_07 AC 39 ms
55,808 KB
testcase_08 AC 74 ms
84,968 KB
testcase_09 AC 45 ms
62,848 KB
testcase_10 AC 68 ms
73,600 KB
testcase_11 AC 131 ms
85,888 KB
testcase_12 AC 106 ms
84,964 KB
testcase_13 AC 104 ms
84,728 KB
testcase_14 AC 104 ms
82,156 KB
testcase_15 AC 103 ms
81,252 KB
testcase_16 AC 93 ms
80,640 KB
testcase_17 AC 95 ms
80,000 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