結果

問題 No.430 文字列検索
ユーザー むらためむらため
提出日時 2019-01-30 22:10:18
言語 Nim
(2.0.2)
結果
AC  
実行時間 152 ms / 2,000 ms
コード長 1,868 bytes
コンパイル時間 2,798 ms
コンパイル使用メモリ 69,028 KB
実行使用メモリ 22,804 KB
最終ジャッジ日時 2023-09-14 03:19:09
合計ジャッジ時間 4,656 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 152 ms
22,432 KB
testcase_02 AC 46 ms
22,600 KB
testcase_03 AC 108 ms
20,944 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 143 ms
20,968 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 13 ms
6,428 KB
testcase_11 AC 139 ms
22,316 KB
testcase_12 AC 137 ms
22,804 KB
testcase_13 AC 140 ms
21,052 KB
testcase_14 AC 133 ms
21,008 KB
testcase_15 AC 131 ms
21,056 KB
testcase_16 AC 89 ms
21,032 KB
testcase_17 AC 72 ms
20,972 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sequtils,algorithm
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) = # [l,r)
    ((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)
    # 67800 と 678 は 67800 == 678 * 100 で得られる
useRollingHash()

let S = stdin.readLine()
let m = scan()
let RH = S.initRollingHash()
var H = newSeqWith(11,newSeq[(int,int)]())
for i in 1..10:
  for j in 0..S.len-i:
    H[i] &= RH.hash(j,j+i)
for i in 1..10: H[i].sort(cmp)
var ans = 0
m.times:
  let S2 = stdin.readLine()
  let h = S2.initRollingHash().hash(0,S2.len)
  ans += H[S2.len].upperBound(h) - H[S2.len].lowerBound(h)
echo ans
0