結果

問題 No.430 文字列検索
ユーザー ptotqptotq
提出日時 2019-08-21 19:54:05
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 504 ms / 2,000 ms
コード長 1,362 bytes
コンパイル時間 354 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 15,796 KB
最終ジャッジ日時 2024-04-17 22:33:40
合計ジャッジ時間 6,485 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
11,008 KB
testcase_01 AC 491 ms
15,796 KB
testcase_02 AC 475 ms
15,792 KB
testcase_03 AC 467 ms
15,668 KB
testcase_04 AC 33 ms
10,880 KB
testcase_05 AC 32 ms
10,880 KB
testcase_06 AC 32 ms
10,880 KB
testcase_07 AC 31 ms
11,008 KB
testcase_08 AC 444 ms
15,012 KB
testcase_09 AC 31 ms
10,880 KB
testcase_10 AC 67 ms
11,264 KB
testcase_11 AC 482 ms
15,796 KB
testcase_12 AC 472 ms
15,792 KB
testcase_13 AC 504 ms
15,796 KB
testcase_14 AC 495 ms
15,792 KB
testcase_15 AC 479 ms
15,792 KB
testcase_16 AC 471 ms
15,796 KB
testcase_17 AC 465 ms
15,664 KB
権限があれば一括ダウンロードができます

ソースコード

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