結果

問題 No.430 文字列検索
コンテスト
ユーザー naniwazu
提出日時 2023-07-30 00:23:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,375 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 82,816 KB
最終ジャッジ日時 2024-11-10 01:06:51
合計ジャッジ時間 3,698 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda:sys.stdin.readline().rstrip()
# https://qiita.com/keymoon/items/11fac5627672a6d6a9f6 より

MASK30 = (1 << 30) - 1
MASK31 = (1 << 31) - 1
MOD = (1 << 61) - 1
MASK61 = MOD
POSITIVIZER = MOD * 4
base = 37

def Mul(a, b): #a * b % (2**61-1)を高速で計算
    au = a >> 31
    ad = a & MASK31
    bu = b >> 31
    bd = b & MASK31
    mid = ad * bu + au * bd
    midu = mid >> 30
    midd = mid & MASK30
    return au * bu % 2 + midu + (midd << 31) + ad * bd # 計算結果はmod*4未満

def CalcMod(x):
    xu = x >> 61
    xd = x & MASK61
    res = xu + xd
    if res >= MOD:
        res -= MOD
    return res

def RollingHash(s):
    l = len(s)
    hash = [0]*(l+1)
    for i in range(l):
        hash[i+1] = CalcMod(Mul(hash[i],  base) + ord(s[i]))
    return hash

# あらかじめ必要な長さの最大値分のPowMemoを計算しておく
def setup_PowMemo(l):
    global PowMemo
    PowMemo = [1]*(l+1)
    for i in range(l):
        PowMemo[i+1] = CalcMod(Mul(PowMemo[i], base))

def get(hash, l, r):
    return CalcMod(hash[r] + POSITIVIZER - Mul(hash[l], PowMemo[r - l]))

S = input()
N = len(S)
setup_PowMemo(N)
RH = RollingHash(S)
M = int(input())

ans = 0
for _ in range(M):
    C = input()
    l = len(C)
    hash = RollingHash(C)[-1]
    for i in range(N-l+1):
        if get(RH, i, i+l) == hash:
            ans += 1

print(ans)
0