#aho-corasick algorithm
import tables

type
  AhoNode = object
    hit: string
    word: bool
    to: Table[int, string]
    fail: string
    failed: bool
type
  AhoCorasick* = object
    tree*: Table[string, AhoNode]
    rootValue: string

proc makeNode*(fail: string, failed: bool): AhoNode =
  result        = AhoNode()
  result.hit    = ""
  result.word   = false
  result.to     = initTable[int, string]()
  result.fail   = fail
  result.failed = failed

proc add*(a: var AhoCorasick, s: string) =
  ## on first letter .fail goes to root
  ## each letter passes path, path = letter + next letter
  ## last letter of string is marked .word = true
  var current    = a.rootValue
  for c in s:
    let asInt = ord(c)
    let path = current & c
    #let wordFlag = path == s ? isWord : isNotAWord

    if a.tree[current].to.hasKey(asInt) == false:
      a.tree[current].to[asInt] = path

      if current == a.rootValue:
        a.tree[path] = makeNode(a.rootValue, true)
      else:
        a.tree[path] = makeNode(a.rootValue, false)

    current = path

  a.tree[s].word = true



proc initialize*(a: var AhoCorasick) =
  ## adds root node, as first/only letter
  ## .fail points to itself and .word is false
  a.tree = initTable[string, AhoNode]()
  a.tree[""] = makeNode(a.rootValue, true)

when isMainModule:
  var aho = AhoCorasick(rootValue: "")
  aho.initialize()
  aho.add("The")

  echo ($aho)