字符串匹配算法

今日，研究了一天的字符串匹配算法，小有所得。主要是从这个链接学习， http://www-igm.univ-mlv.fr/~lecroq/string/

理论上，这里算法都比glibc中strstr的算法复杂度小，但在实际场景中，特别是和目前的开发的产品中关键字匹配场景下，无论是Boyer-Moore还是Knuth-Morris-Pratt等这些经典的算法实现都比strstr慢得多，而strstr的默认算法仅是一种高度优化过的Brute Force实现（Linux下C的测试结果证明如此，java下根据默认string.IndexOf算法看来，可能另有差别，需要进一步证明）。

目前得到一点结论是，这些经典的算法中都有预处理阶段，而Brute Force实现并无此阶段，当是预处理阶段耗时较多造成的差别。

（从200字节中查找20字节字符串1000000次， strstr:0ms, 其它最优的实现是250ms+）