結果

問題 No.430 文字列検索
ユーザー Goro Kobayashi
提出日時 2019-11-21 14:11:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 825 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 94,720 KB
最終ジャッジ日時 2024-11-10 00:38:17
合計ジャッジ時間 3,703 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**7)

alpha_dic = {}
for i,a in zip(range(1,27),"ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
    alpha_dic[a] = i

def hash(before,rm,ad,length):
    if before:
        return (before - alpha_dic[rm]*(27**(length-1)))*27 + alpha_dic[ad]
    else:
        ans = 0
        for i,a in enumerate(ad):
            ans += alpha_dic[a] * 27**(length-1-i)
        return ans

S = input()
M = int(input())
count = 0
for _ in range(M):
    c = input()
    length = len(c)
    hashed_c = hash(None,None,c,length)
    s = S[:length]
    hashed_s = hash(None,None,s,length)
    if hashed_c ==  hashed_s:
        count += 1
    for x in S[length:]:
        rm = s[0]
        s = s + x
        s = s[1:]
        hashed_s = hash(hashed_s,rm,x,length)
        if hashed_c ==  hashed_s:
            count += 1
print(count)
0