結果

問題 No.430 文字列検索
ユーザー ptotqptotq
提出日時 2019-08-21 19:28:55
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,355 bytes
コンパイル時間 846 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 15,768 KB
最終ジャッジ日時 2024-11-10 00:29:31
合計ジャッジ時間 5,095 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 26 ms
10,752 KB
testcase_01 WA -
testcase_02 AC 378 ms
15,640 KB
testcase_03 AC 378 ms
15,632 KB
testcase_04 AC 27 ms
10,880 KB
testcase_05 AC 25 ms
10,880 KB
testcase_06 AC 25 ms
10,752 KB
testcase_07 AC 26 ms
10,880 KB
testcase_08 AC 338 ms
14,852 KB
testcase_09 AC 27 ms
10,752 KB
testcase_10 AC 54 ms
11,136 KB
testcase_11 AC 369 ms
15,756 KB
testcase_12 AC 369 ms
15,764 KB
testcase_13 AC 363 ms
15,624 KB
testcase_14 AC 369 ms
15,768 KB
testcase_15 AC 377 ms
15,768 KB
testcase_16 AC 381 ms
15,628 KB
testcase_17 AC 394 ms
15,636 KB
権限があれば一括ダウンロードができます

ソースコード

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__':
    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