結果

問題 No.430 文字列検索
コンテスト
ユーザー むらため
提出日時 2019-01-30 21:47:28
言語 Nim
(2.2.0)
結果
TLE  
実行時間 -
コード長 1,720 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,031 ms
コンパイル使用メモリ 62,040 KB
実行使用メモリ 11,172 KB
最終ジャッジ日時 2024-11-10 00:21:58
合計ジャッジ時間 6,903 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 8) Warning: imported and not used: 'sequtils' [UnusedImport]

ソースコード

diff #
raw source code 

import sequtils
template times*(n:int,body) = (for _ in 0..<n: body)

proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}
proc scan(): int =
  while true:
    let k = getchar_unlocked()
    if k < '0': break
    result = 10 * result + k.ord - '0'.ord

template useRollingHash() =
  type RollingHash = object
    A,B: seq[int]
    AP,BP: seq[int]
    modA,modB : int
    baseA,baseB : int
  proc initRollingHash(
      S:string, baseA:int=17, baseB:int=19,
      modA:int=1_0000_0000_7.int, modB:int=1_0000_0000_9.int) : RollingHash =
    result.baseA = baseA
    result.baseB = baseB
    result.modA = modA
    result.modB = modB
    result.A = newSeq[int](S.len + 1) # baseA 進数表示した時の値
    result.B = newSeq[int](S.len + 1)
    result.AP = newSeq[int](S.len + 1) # base^n
    result.BP = newSeq[int](S.len + 1)
    result.AP[0] = 1
    result.BP[0] = 1
    for i in 0..<S.len: result.A[i+1] = (result.A[i] * baseA + S[i].ord) mod modA
    for i in 0..<S.len: result.B[i+1] = (result.B[i] * baseB + S[i].ord) mod modB
    for i in 0..<S.len: result.AP[i+1] = (result.AP[i] * baseA) mod modA
    for i in 0..<S.len: result.BP[i+1] = (result.BP[i] * baseB) mod modB
  proc hash(self:RollingHash,l,r:int):(int,int) = # 67800 と 678 は 67800 == 678 * 100 で得られる
    ((self.AP[r-l] * self.A[l] - self.A[r] + self.modA) mod self.modA,
    (self.BP[r-l] * self.B[l] - self.B[r] + self.modB) mod self.modB)
useRollingHash()

let S = stdin.readLine()
let m = scan()
let RH = S.initRollingHash()
var ans = 0
m.times:
  let S2 = stdin.readLine()
  let h = S2.initRollingHash().hash(0,S2.len)
  for i in 0..S.len - S2.len:
    if RH.hash(i,i+S2.len) == h : ans += 1
echo ans
0