結果

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

ソースコード

diff # 

L=50000

B=123451234512345
M=(1<<61)-1
P=[1,B]
R=[1,pow(B,M-2,M)]
for i in range(2,L+1):
  P+=[P[-1]*P[1]%M]
  R+=[R[-1]*R[1]%M]

class RH():
  def __init__(self,s):
    self.len=len(s)
    self.h=[0]*(len(s)+1)
    for i in range(self.len):
      self.h[i]=(ord(s[i])*P[i]+self.h[i-1])%M
    return
  def rh(self,l,r):
    return (self.h[r]-self.h[l-1])*R[l]%M

S=RH(input())
L=S.len
n=int(input())
c=0
for _ in range(n):
  t=RH(input())
  l=t.len
  for i in range(L-l+1):
    c+=S.rh(i,i+l-1)==t.rh(0,l-1)

print(c)
0