https://pdfs.semanticscholar.org/131f/fb9667e736de2b46a7dac9a83fbe996e53b2.pdf?_ga=1.1647415.70467011.1445300274 (incomplete)

SuffixTree.scala

object SuffixTree extends App {
  case class TreeNode(children: Map[Char, TreeNode] = Map.empty, end: Boolean = false) {

    def addString(string: CharSequence): TreeNode = {
      if(string.length() == 0) {
        this.copy(end = true)
      } else {
        val c = string.charAt(0)
        val existingNode = children.getOrElse(c, TreeNode())
        this.copy(children = children.updated(c, existingNode.addString(string.subSequence(1, string.length()))))
      }
    }

    def print(indent: Int = 0): Unit = {
      val indentString = List.fill(indent)(' ').mkString
      children.foreach { case (char, node) =>
        val endString = if(node.end) "$" else ""
        println(s"$indentString$char$endString")
        node.print(indent + 1)
      }
    }
  }

  def naiveConstruction(string: CharSequence): TreeNode = {
    val suffixes = (0 to string.length()).map(string.subSequence(_, string.length()))
    suffixes.foldLeft(TreeNode()) { case (rootNode, s) => rootNode.addString(s) }
  }

  val testString = "babas"

  val result = naiveConstruction(testString)
  result.print()
}

object UkkonenSuffixTree extends App {
  trait State {
    def suffixLink: State
    def links: Map[Char, State]
  }

  case class RealState(links: Map[Char, State], suffixLink: State)

  class BottomState extends State {
    override def suffixLink = ???
    override val links = Map('∑' -> RealState(Map.empty, this))
  }
}