結果

問題 No.430 文字列検索
ユーザー sasa8uyauyasasa8uyauya
提出日時 2024-09-29 21:58:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 227 ms / 2,000 ms
コード長 651 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 109,080 KB
最終ジャッジ日時 2024-11-10 01:13:16
合計ジャッジ時間 3,302 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 60 ms
78,848 KB
testcase_01 AC 227 ms
109,080 KB
testcase_02 AC 159 ms
82,048 KB
testcase_03 AC 157 ms
82,048 KB
testcase_04 AC 62 ms
79,104 KB
testcase_05 AC 61 ms
78,720 KB
testcase_06 AC 61 ms
78,720 KB
testcase_07 AC 61 ms
78,976 KB
testcase_08 AC 189 ms
107,968 KB
testcase_09 AC 67 ms
80,512 KB
testcase_10 AC 84 ms
81,024 KB
testcase_11 AC 179 ms
83,456 KB
testcase_12 AC 180 ms
83,840 KB
testcase_13 AC 178 ms
83,584 KB
testcase_14 AC 171 ms
81,920 KB
testcase_15 AC 167 ms
82,176 KB
testcase_16 AC 160 ms
82,048 KB
testcase_17 AC 165 ms
82,048 KB
権限があれば一括ダウンロードができます

ソースコード

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
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