KMP算法
Wednesday, April 11th, 2007
KMP是字符串匹配的高效算法。
它的基本思路是，对于模式串建立一个“失败转移表”(fail transform table)。设模式串为B，原串为A，也就是说，当A[i]!=B[j]的时候，A[i]可能与B[P[j]]匹配。
P可以在事先对B进行一次“自匹配”以计算出来。我们看到的KMP总是两段很相似的代码。
今天写KMP的时候开始老写错，最后没办法了上Google Code Search搜索了一下KMP，参考或者说抄袭了一下排在第一的libg++里面的代码……这大约是有点悖德的事情，不过显然我也顾不得那么多了现在。
程序：ural1423.cpp
Tags: KMP, 算法
Related posts
求最大流的使用距离标号的最短增广路算法
最小树形图
平衡二叉查找树
矩阵乘法
利用 Sparse Table 构造 Suffix Array