結果

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

ソースコード

diff # 

class RollingHash(object):
    ZERO = ord('A')-1
    MAX_V = ord('Z')+1
    BASE = MAX_V - ZERO + 1
    MOD = 67280421310721

    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__':
    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+11, len_s+1)):
            ans += rh.get_hash(l, r) in subs

    print(ans)
0