简单实现了一个Trie

用Kotlin和OOP的写法，也许比OI风格的代码可读性更好吧。

这是代码片段，总的来说，感觉class和封装能够更好地让代码具有自描述的能力，稍微留心一下把变量名和函数名取好的话，其实并不需要很多注释。这里写注释更多是为了记下思路，或者算是教学目的的了。

data class TrieNode(val char: Char?, val children: MutableList<TrieNode> = mutableListOf()) {
  // Trie由嵌套的Node组成，每一层Node都包含一个char字段和子节点列表，这里假设字符插入后就不能改变

  // 为了简化树的构造，char可以为空，这样的话第一个节点的char标记为null，只用来作为构造Trie的entrypoint
  // 当然这个思路下Trie的各种方法也需要微调了

  /**
   * 私有方法，为当前的Trie拼接一个子节点，并且确保不会在同一个节点下有两个指向同一个字符的子节点
   */
  private fun append(node: TrieNode): TrieNode {
    if (children.none { it.char == node.char }) {
      children.add(node)
      return node
    } else {
      throw IllegalStateException("Double child detected")
    }
  }

  /**
   * 私有方法，给定一个字符串，查看当前节点的直接子节点是否有匹配的
   */
  private fun lookup(c: Char) = children.firstOrNull { it.char == c }

  /**
   * 往Trie里插入整个字符串，会调用前面的私有方法
   */
  fun insert(s: String): Unit {
    // 需要特别对待字符串为空的情况
    if (s.isNotEmpty()) {
      // 这里的思路很简单，查询当前节点下匹配字符串第一个字母的子节点，没有的话创建一个
      val firstNode = lookup(s.first()) ?: append(TrieNode(s.first()))
      // 递归调用，逐层去掉首字母地插入字符串
      firstNode.insert(s.drop(1))
    }
  }

  /**
   * 查询构建的Trie里是否以给定的字符串开始
   */
  fun find(s: String): Boolean {
    return if (s.isNotEmpty()) {
      // 查询当前节点下是否有匹配字符串对应位置的子节点
      lookup(s.first())?.find(s.drop(1)) ?: false
    } else {
      // 需要特别对待字符串为空的情况
      true
    }
  }
}

要从一个字符串构建出对应的Trie，也就是把这个字符串的所有后缀都输入进去：

// 构建后缀Trie的helper函数
fun buildSuffixTrie(s: String): TrieNode {
  val topTree = TrieNode(null)

  for (i in s.indices) {
    topTree.insert(s.slice(i..< s.length))
  }

  return topTree
}

大概是这样：

val trie = buildSuffixTrie("quickfoxjump")

trie.find("quickfox").let(::println) // true
trie.find("quickdog").let(::println) // false

也可以手动构建：

val topTree = TrieNode(null)

topTree.insert("aa")
topTree.insert("aba")
topTree.insert("ba")
topTree.insert("caa")
topTree.insert("cab")
topTree.insert("aba")
topTree.insert("cc")
topTree.insert("caab")

topTree.find("caab")

总的来讲，这套写法性能和效率都不怎么样，哪怕纯OOP也有效率更高的（比如使用标准库的字典或数组，减少链式调用或字符串上的方法的使用，用更多的循环，之类的）。但总体来说效率也还过得去。

主要还是可读性会比较好。

当然Trie也算一种比较简单的数据结构，如果能够实现效率更好的后缀树数据结构的话，也算一种提升。

这次大概就先到这里了。