結果

問題 No.430 文字列検索
ユーザー HAMASHITAHAMASHITA
提出日時 2022-04-19 22:41:33
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 1,310 bytes
コンパイル時間 82 ms
コンパイル使用メモリ 10,928 KB
実行使用メモリ 15,036 KB
最終ジャッジ日時 2023-08-30 20:39:30
合計ジャッジ時間 3,650 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 15 ms
15,036 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 # 

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