标准trie树应用之串的快速检索

缘起

trie树又称为字典树、前缀树. 它是AC自动机算法的基础（关于AC自动机后面我会写文章）. 不过说到这里，我不得不补充一下，为什么字符串算法在算法中的地位那么的高? 因为不论计算机技术发展的如何日新月异，高速迅猛. 软件技术离不开三件东西

  1. 编译原理
  2. 操作系统
  3. 网络原理

而它们三者之基石就是无关具体技术，而纯在思想层面的——数据结构和算法（足见数据结构和算法之重要性）. 而编译原理其实就是在处理规则化的人类语言——高级编程语言（如C/C++、Java、Python等等），将高级编程语言变成机器可以“懂”的语言. 这个过程（不论是生成机器码的过程还是生成机器码的执行的过程）关系到代码的高效程度（也就是所谓代码的质量）. 所以你说字符串算法重不重要? 字符串算法往大了说，就是展示、解析、转换信息的算法. 人类的文明无不是建立在信息的基础之上. 在海量信息的今天，高效字符串处理——不论是不是计算机层面的，都日益重要. 我是不是逼话多了点?

它的典型应用如下

1
2
给定n个单词组成熟词表T，以及一篇全用英文小写字母组成的文章，请你按照最早出现的顺序写出所有不在T中的生
词.

Read More

自己写仅包含加号、乘号、小括号、正整数数字的表达式的编译器

缘起

最近在看Coding 迪士尼老师的《自己动手用java写编译器》视频教程（一直想入手编译原理这门课，但是大部分书籍太理论化了, 深深的感觉无力，看到这门课，眼前一亮~ 有门了~）. 看了前三集，觉得思想不错，就是代码实现风格不是很赞同. 遂停下观看，针对前三集，自己写一个仅包含加号、乘号、小括号、正整数数字的表达式的编译器. 不然前三集仅仅弄懂思想，却没有自己手写实现的代码，我依旧感觉很无力. 我贯彻的思想是——没有代码的算法思想是耍流氓. 本文作为该视频教程前三集的总结.

Read More