前一段时间，在将 多正则表达式匹配工具 用于数十万任意的正则表达式时，以前一直担心的问题终于出现了：NFA 转化 DFA 时的指数爆炸，那样的 DFA 根本创建不出来，因为那些正则表达式之间有不可预料的各种交集！ 继续阅读 →

这个工具使用了一个非常高效的算法，用来匹配多个高级正则表达式。经过预处理，仅用 O(n) 的时间复杂度，就可以识别出一个输入字符串（长度为n）能匹配哪些（可能是多个）正则表达式。算法的详细内容可参见：

继续阅读 →

最近做了一项工作：允许一个 DFA 有多个起始状态（可以称作根: root）。引入这个概念有很多好处，主要体现在 DFA Union 中，这个操作通过 NFA 到 DFA 的转化来完成，算法思想很简单： 继续阅读 →

昨天一个朋友 checkout 了我的 febird 代码，编译时出现了一个诡异的错误。经过仔细勘察，他的 g++ 版本是 4.7.3，而我测试过的 g++4.7.2，g++4.8.2均无问题。 继续阅读 →

目前 febird 中的自动机库已支持正则表达式，并且，支持的是多正则表达式匹配： 继续阅读 →

刚才开始用 boost::range，就查看了了一下 boost 源码，发现 boost-1.50 一个 bug，觉得应该在新版中已经修改了，下载了最新的 1.54 版，进去一看，bug 仍然在！ 继续阅读 →

这篇文档只关心 有穷状态自动机 ，不讲具体的算法，对自动机只讲一些基本概念。主要描述 怎样使用自动机工具创建 KV 数据库，怎样使用自动机 API 访问 KV 数据库…… 继续阅读 →

在我以前的这篇文章中：原地排序与链表翻转

解决这个问题是先把链表翻转，然后再循环左移，原理是清楚了，可是稍显繁琐。今天得知该问题的另一个解法： 继续阅读 →

有一个字符串由多个变量拼接而成： “$x1$x2$x3$x4$x5$x6…” ，这个列表可以一直延伸到 $x10000，而每个变量都至少有一种可能的取值，为了简化问题，每个变量不会再引用别的变量。问题是：给定一个字符串T，判断这个字符串是否能由上面这个 “$x1$x2$x3$x4$x5$x6…” 生成。

继续阅读 →

《一生紧随毛：回忆我的父亲…陈士榘》里记载，“李德刚刚来到部队，提出…希望有个中国女战士陪他睡觉。”
康…说：“当时女同志都不愿意嫁给一个不会说中国话的外国人，所以一直找不到合适的对象。”后来找到个“大个子，长得不错的前童养媳。”萧月华1910年8月出生于广东大埔县一个农民家庭。
继续阅读 →