結果

問題 No.430 文字列検索
ユーザー naniwazunaniwazu
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
57,984 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
権限があれば一括ダウンロードができます

ソースコード

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