結果

問題 No.430 文字列検索
ユーザー はむ吉🐹はむ吉🐹
提出日時 2016-10-09 13:28:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 935 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 147,712 KB
最終ジャッジ日時 2024-05-01 15:42:17
合計ジャッジ時間 3,654 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

#!/usr/bin/env pypy3


def str2array(s):
    assert s.islower() or s.isupper()
    s = s.lower()
    a = ord("a")
    return [ord(c) - a for c in s]


# 参考：『アルゴリズムイントロダクション』（第3版）pp.823-827
def rabin_karp_matcher(text, pattern, q=1000000007):
    D = 26
    txt = str2array(text)
    ptn = str2array(pattern)
    n = len(txt)
    m = len(ptn)
    if n < m:
        return
    h = pow(D, m - 1, q)
    p = 0
    t = 0
    for i in range(m):
        p = (D * p + ptn[i]) % q
        t = (D * t + txt[i]) % q
    for s in range(n - m + 1):
        if p == t and ptn[:m] == txt[s:s + m]:
            yield s
        if s < n - m:
            t = (D * (t - txt[s] * h) + txt[s + m]) % q


def main():
    s = input()
    m = int(input())
    cs = [input() for _ in range(m)]
    ans = sum(len(list(rabin_karp_matcher(s, c))) for c in cs)
    print(ans)


if __name__ == '__main__':
    main()
0