結果

問題 No.430 文字列検索
コンテスト
ユーザー はむ吉🐹
提出日時 2016-10-09 13:28:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 935 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 82,556 KB
実行使用メモリ 154,904 KB
最終ジャッジ日時 2024-11-10 00:10:10
合計ジャッジ時間 3,594 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

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