結果

問題 No.430 文字列検索
コンテスト
ユーザー moharan627
提出日時 2021-07-02 15:38:06
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 4,409 bytes
コンパイル時間 484 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 22,528 KB
最終ジャッジ日時 2024-11-10 00:57:01
合計ジャッジ時間 3,513 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

INF = float('inf')
#10**20,2**63に変えるのもあり
MOD = 10**9 + 7
MOD2 = 998244353
from random import randrange
class RollingHash:
    def __init__(self, s):
        # baseは原始根だよ
        self.base = [37, 368789449308, 1852846309939, 2102001800968, 3135613673210,
                     3573032120887, 5162739766272, 5981870488812, 6752369793223, 7700519273161,
                     9299907180755, 11220764879935, 13661711890983, 15631445301958, 16191225434172,
                     17992903178549, 18444241224682, 19542925735378, 19904897765689, 21026451511176,
                     22352021740951, 24614951263776, 27926655860868, 28668013049122, 30731186880431,
                     31200962432156, 32525487701018, 33195339867934, 34424470708402, 35347625139334,
                     35538747926358, 35582135363245, 38299872411055, 39611488430368, 39640191188389,
                     39687840340713, 39836964525889, 40494045054405, 41823714436906, 42464338718658,
                     45187222874290, 46814471362845, 46843887310593, 47056835891494, 47120526022187,
                     47245858682046, 48060903655667, 49148836433744, 50740362522447, 52092287614654,
                     52963661986595, 53909010970445, 54034266176372, 56610716098501, 57249192258849,
                     58159353606107, 58265735653900, 59020252957603, 60035782095813, 60299921283817,
                     61190794855394, 64063255668212, 66214433217808, 66216096723703, 67780144096898,
                     67999945148190, 68256362212749, 70499107424943, 70862334850448, 72011752626580,
                     73649428254369, 75449903238572, 76548613569443, 78278540023804, 79009260751099,
                     80099977091766, 80465655308476, 83855206194524, 92017907719628, 92059595206125,
                     92062781387242, 92471692941349, 92498823585506, 93431743820951, 94923662069170,
                     95089788205304, 96760468270869, 97437512252944, 98969648473851, 101584354600387,
                     103992426667469, 104570401503026, 105149646660817, 106163858477891, 106970744616241,
                     107019066406563, 107140499986715, 108680210682305, 109288626609043, 110027486424350][
            randrange(0, 100)]
        self.mod = 2305843009213693951  # 2**61 - 1
        self.size = len(s)
        self.string = s

        self.hash = self.__make_hashtable(s)
        self.pow = self.__make_powtable()

    def __make_hashtable(self, _s):
        hashtable = [0] * (self.size + 1)
        for i in range(self.size):
            hashtable[i + 1] = (hashtable[i] * self.base + ord(_s[i])) % self.mod
        return hashtable

    def __make_powtable(self):
        power = [1] * (self.size + 1)
        for i in range(self.size):
            power[i + 1] = (self.base * power[i]) % self.mod
        return power

    def get_hash(self, left, right):
        """get hash of s[left:right]"""
        return (self.hash[right] - self.hash[left] * self.pow[right - left]) % self.mod

    def contain(self, a):
        """return all s.index(a)"""
        m = len(a)
        hasha = 0
        index = []
        if m > self.size:
            return index
        for i in range(m):
            hasha = (hasha * self.base + ord(a[i])) % self.mod
        for i in range(self.size - m + 1):
            hashs = self.get_hash(i, m + i)
            if hasha == hashs:
                index.append(i)
        return index

    def is_contain(self, a):
        """return a in s"""
        m = len(a)
        if m > self.size:
            return False
        hasha = 0
        for i in range(m):
            hasha = (hasha * self.base + ord(a[i])) % self.mod
        for i in range(self.size - m + 1):
            hashs = self.get_hash(i, m + i)
            if hasha == hashs:
                return True
        return hasha == hashs

def solve():
    def II(): return int(sys.stdin.readline())
    def LI(): return list(map(int, sys.stdin.readline().split()))
    def LC(): return list(input())
    def IC(): return [int(c) for c in input()]
    def MI(): return map(int, sys.stdin.readline().split())
    S = input()
    M = II()
    Rh = RollingHash(S)
    Ans = 0
    for m in range(M):
        C = input()
        List = Rh.contain(C)

        Ans += len(List)
    print(Ans)
    return
solve()
#sys.setrecursionlimit(10 ** 6)再帰関数ではコメントにしないこと！！
0