KMP算法

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