ドドスコテスト KMP法

dodosuko.nim

import std/random
import std/tables
import std/sets
import sequtils

type Dodosuko = enum
  Dodo = "ドド"
  Suko = "スコ"
  DSNil = ""

# code for KMP
# ----------------------------------------
type KmpDfa[A] {.byref.} = object
  dict: seq[Table[A, int]]
  state: int

proc initKmpDfa*[A](dfa: var KmpDfa[A], word: openarray[A]) =
  dfa.state = 0

  var letters: HashSet[A] = word.toHashSet()
  let n: int = word.len()
  dfa.dict = newSeqWith(n + 1, initTable[A, int]())
  var fail: seq[int] = newSeqWith(n, 0)

  for i in 0 ..< word.len():
    for j in 1 ..< i:
      if word[fail[i]] == word[j]:
        fail[i] += 1
      else:
        fail[i] = 0

  for i in 0 ..< word.len():
    for lt in letters:
      if word[i] == lt:
        dfa.dict[i][lt] = i + 1
        continue

      if lt in dfa.dict[fail[i]]:
        dfa.dict[i][lt] = dfa.dict[fail[i]][lt]

proc genKmpDfa*[A](word: openarray[A]): KmpDfa[A] =
  initKmpDfa(result, word)

proc moveKmpDfa*[A](dfa: var KmpDfa[A], letter: A) =
  dfa.state = dfa.dict[dfa.state].getOrDefault(letter, 0)

proc isAcceptKmpDfa*[A](dfa: KmpDfa[A]): bool =
  result = dfa.state == (dfa.dict.len() - 1)
# ----------------------------------------

proc main() =
  var dodosuko33: seq[Dodosuko] = cycle([Dodo, Suko, Suko, Suko], 3)
  const love: string = "ラブ注入♡"

  var dfa: KmpDfa[Dodosuko] = genKmpDfa(dodosuko33)

  randomize()

  while true:
    let next = sample([Dodo, Suko])
    stdout.write next

    dfa.moveKmpDfa(next)

    if dfa.isAcceptKmpDfa():
      echo love
      break

if isMainModule:
  main()