結果

問題 No.430 文字列検索
ユーザー nadeshinonadeshino
提出日時 2019-08-04 07:25:59
言語 Nim
(2.0.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,338 bytes
コンパイル時間 823 ms
コンパイル使用メモリ 72,292 KB
最終ジャッジ日時 2024-04-27 02:53:29
合計ジャッジ時間 1,252 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
stack trace: (most recent call last)
Main.nim(7, 9)           unpack
/home/judge/data/code/Main.nim(55, 20) template/generic instantiation of `input` from here
/home/judge/data/code/Main.nim(15, 30) template/generic instantiation of `unpack` from here
/home/judge/data/code/Main.nim(7, 9) Error: index 1 not in 0 .. 0

ソースコード

diff # 

import algorithm, sugar, macros, math, sequtils, sets, strutils, tables


macro unpack(rhs: seq, cnt: static[int]): auto =
  let t = genSym(); result = quote do:(let `t` = `rhs`;())
  if NimMinor <= 17:
    for i in 0..<cnt: result[0][1].add(quote do:`t`[`i`])
  else:
    for i in 0..<cnt: result[1].add(quote do:`t`[`i`])

template input(T: typedesc, cnt: Natural = 1): untyped =
  let line = stdin.readLine.split(" ")
  when T is int:         line.map(parseInt).unpack(cnt)
  elif T is float:       line.map(parseFloat).unpack(cnt)
  elif T is string:      line.unpack(cnt)
  elif T is char:        line.mapIt(it[0]).unpack(cnt)
  elif T is seq[int]:    line.map(parseint)
  elif T is seq[float]:  line.map(parseFloat)
  elif T is seq[string]: line
  elif T is seq[char]:   line.mapIt(it[0])

proc `%=`(n: var int, m: int)  = n = n mod m
proc `//=`(n: var int, m: int) = n = n div m
proc `<<=`(n: var int, m: int) = n = n shl m
proc `>>=`(n: var int, m: int) = n = n shr m
proc `<?=`(n: var int, m: int) = n = min(n, m)
proc `>?=`(n: var int, m: int) = n = max(n, m)
proc newSeq2[T](n1, n2: Natural): seq[seq[T]] = newSeqWith(n1, newSeq[T](n2))
proc newSeq3[T](n1, n2, n3: Natural): seq[seq[seq[T]]] = newSeqWith(n1, newSeqWith(n2, newSeq[T](n3)))

# -------------------------------------------------- #

const base = 1550606
const modulus = 1000000007

type RollingHash = object
  hashed: seq[int]
  power: seq[int]

proc initRollingHash(S: string): RollingHash =
  let N = S.len() - 1
  result.hashed = newSeq[int](N + 1)
  result.power = newSeq[int](N + 1)
  result.power[0] = 1
  for i in countup(1, N):
    result.hashed[i] = (result.hashed[i - 1] * base + ord(S[i])) mod modulus
    result.power[i] = result.power[i - 1] * base mod modulus

proc toHash(self: RollingHash, l: Natural, r: Natural): int =
  result = (self.hashed[r] - self.hashed[l - 1] * self.power[r - l + 1]) mod modulus
  if result < 0: result += modulus

# -------------------------------------------------- #

var S = "#" & input(string)
var M = input(int)
var shash = initRollingHash(S)
var k = S.len() - 1
var res = 0
for query in 1 .. M:
  var C = "#" & input(string)
  var chash = initRollingHash(C)
  var l = C.len() - 1
  if k < l:
    continue
  for i in 1 .. (k - l + 1):
    if shash.toHash(i, i + l - 1) == chash.toHash(1, l):
      inc res
echo res
0