結果

問題 No.430 文字列検索
ユーザー ptotq
提出日時 2019-08-21 19:18:57
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,391 bytes
コンパイル時間 789 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 15,904 KB
最終ジャッジ日時 2024-11-10 00:29:33
合計ジャッジ時間 4,442 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

class RollingHash(object):
    ZERO = ord('A')-1
    MAX_V = ord('Z')+1
    BASE = MAX_V - ZERO + 1
    MOD = 10**9+7

    def __init__(self, source: str):
        zero, base, mod = self.ZERO, self.BASE, self.MOD

        self.coef = coef = [0, base]
        self.hash_list = hash_list = [0, ord(source[0])-zero]
        hash_append, coef_append = hash_list.append, coef.append

        for x in map(ord, source[1:]):
            hash_append((hash_list[-1] * base + (x-zero)) % mod)
            coef_append(coef[-1] * base % mod)

    def get_hash(self, l: int, r: int):
        return (self.hash_list[r] -
                self.hash_list[l] * self.coef[r-l]) % self.MOD

    def is_same(self, l: int, r: int, hash_value: int):
        return hash_value == self.get_hash(l, r)

    @classmethod
    def calc_hash(cls, source: str):
        zero, base, mod = cls.ZERO, cls.BASE, cls.MOD
        hash_value = 0

        for x in map(ord, source):
            hash_value = (hash_value * base + x - zero) % mod

        return hash_value


if __name__ == '__main__':
    import time
    t = time.time()
    S = input()
    len_s = len(S)
    rh = RollingHash(S)
    M = int(input())
    subs = {rh.calc_hash(s) for s in (input() for _ in [0]*M)}
    ans = 0

    for l in range(len_s):
        for r in range(l+1, min(l+10, len_s+1)):
            ans += rh.get_hash(l, r) in subs

    print(ans)
0