結果

問題 No.430 文字列検索
ユーザー ptotqptotq
提出日時 2019-08-21 19:18:57
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,391 bytes
コンパイル時間 90 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 15,904 KB
最終ジャッジ日時 2024-04-17 19:46:12
合計ジャッジ時間 5,162 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
11,008 KB
testcase_01 AC 394 ms
15,648 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 29 ms
10,880 KB
testcase_05 AC 28 ms
10,880 KB
testcase_06 AC 28 ms
10,880 KB
testcase_07 AC 28 ms
10,752 KB
testcase_08 AC 341 ms
15,128 KB
testcase_09 AC 29 ms
10,752 KB
testcase_10 AC 63 ms
11,136 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
権限があれば一括ダウンロードができます

ソースコード

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