本文共 306 字，大约阅读时间需要 1 分钟。

字符串匹配问题：求出模板在文本中的所有匹配点，所谓匹配点是指从当前点开始，在模板的长度内，模板与文本字符一样。

朴素的字符串匹配，当模板与文本不匹配时，模板右移一位然后，从模板0位置开始继续检测当前文本点是否是匹配点。复杂度n*m。

KMP匹配：

核心思想：当模板与文本在某点不匹配时，不是模板重新开始从下标0开始进行匹配，而是充分利用文本中已经匹配过的字符串，构造一个失配函数F[i]表示当文本与模板的i位置失配时，文本s可能与模板t的f[i]位置匹配。比如对于模板abbaaba来说，当文本与模板在下标[6]=a处发生失配(说明5及之前都是匹配的)，那么我们可以直接接着比较模板t[2]与当前的文本是否匹配。

转载地址：http://oogsi.baihongyu.com/