結果

問題 No.430 文字列検索
コンテスト
ユーザー sasa8uyauya
提出日時 2024-09-29 21:58:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 227 ms / 2,000 ms
コード長 651 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 216 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 109,080 KB
最終ジャッジ日時 2024-11-10 01:13:16
合計ジャッジ時間 3,302 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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
d=[{} for i in range(11)]
for l in range(1,11):
  for i in range(L-l+1):
    p=S.rh(i,i+l-1)
    if p not in d[l]:
      d[l][p]=0
    d[l][p]+=1
n=int(input())
c=0
for _ in range(n):
  t=RH(input())
  l=t.len
  p=t.rh(0,l-1)
  if p in d[l]:
    c+=d[l][p]

print(c)
0