結果

問題 No.430 文字列検索
ユーザー むらためむらため
提出日時 2019-02-04 09:17:33
言語 Nim
(2.0.2)
結果
AC  
実行時間 172 ms / 2,000 ms
コード長 1,925 bytes
コンパイル時間 2,819 ms
コンパイル使用メモリ 69,116 KB
実行使用メモリ 21,464 KB
最終ジャッジ日時 2023-09-14 03:28:42
合計ジャッジ時間 5,674 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 172 ms
21,072 KB
testcase_02 AC 55 ms
21,224 KB
testcase_03 AC 120 ms
21,092 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 165 ms
21,012 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 16 ms
6,456 KB
testcase_11 AC 161 ms
21,104 KB
testcase_12 AC 160 ms
21,120 KB
testcase_13 AC 160 ms
21,464 KB
testcase_14 AC 155 ms
21,060 KB
testcase_15 AC 149 ms
21,076 KB
testcase_16 AC 106 ms
21,124 KB
testcase_17 AC 85 ms
21,084 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() = # 構築 O(|S|) / 部分文字列検索 O(1)
  type RollingHash = ref object
    modA,modB : int
    baseA,baseB : int
    A,B: seq[int]  # baseA 進数表示
    AP,BP: seq[int] # pow(baseA,n)
  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 =
    new(result)
    result.baseA = baseA
    result.baseB = baseB
    result.modA = modA
    result.modB = modB
    result.A = newSeq[int](S.len + 1)
    result.B = newSeq[int](S.len + 1)
    result.AP = newSeq[int](S.len + 1)
    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