結果

問題 No.430 文字列検索
ユーザー Goro KobayashiGoro Kobayashi
提出日時 2019-11-21 14:11:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 825 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 57,984 KB
最終ジャッジ日時 2024-04-18 02:23:53
合計ジャッジ時間 3,804 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
57,984 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
権限があれば一括ダウンロードができます

ソースコード

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