結果

問題 No.430 文字列検索
コンテスト
ユーザー proribone
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

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