結果

問題 No.430 文字列検索
コンテスト
ユーザー HAMASHITA
提出日時 2022-04-19 22:41:33
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,310 bytes
コンパイル時間 77 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 16,384 KB
最終ジャッジ日時 2024-11-10 00:59:52
合計ジャッジ時間 3,456 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

alphabet_to_int = {
    'A': 1,
    'B': 2,
    'C': 3,
    'D': 4,
    'E': 5,
    'F': 6,
    'G': 7,
    'H': 8,
    'I': 9,
    'J': 10,
    'K': 11,
    'L': 12,
    'M': 13,
    'N': 14,
    'O': 15,
    'P': 16,
    'Q': 17,
    'R': 18,
    'S': 19,
    'T': 20,
    'U': 21,
    'V': 22,
    'W': 23,
    'X': 24,
    'Y': 25,
    'Z': 26
}
def count_string(s: str, t: str):
    """
    Rolling hash function
    """
    count = 0
    n = len(s)
    m = len(t)
    if n < m:
        return 0
    base = 26
    mod = 10 ** 9 + 7
    t_hash = 0
    for i, c in enumerate(t):
        t_hash += alphabet_to_int[c] * (base ** (m - i - 1)) % mod
        t_hash %= mod

    s_hash = 0 
    for i in range(m):
        s_hash += alphabet_to_int[s[i]] * (base ** (m - i - 1))
        s_hash %= mod
    if s_hash == t_hash:
        count += 1

    # rolling hash
    for i in range(1, len(s) - m + 1):
        s_hash = s_hash * base - alphabet_to_int[s[i - 1]] * (base ** m) + alphabet_to_int[s[i + m - 1]]
        s_hash %= mod
        if s_hash == t_hash:
            count += 1

    return count


if __name__ == "__main__":
    s = str(input()) 
    m = int(input())
    t_array = [str(input()) for _ in range(m)]
    result = 0
    for t in t_array:
        result += count_string(s, t)


    print(result)
0