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

超详细的KMP算法

一.暴力算法(BF算法)

假设我们现在要对上面的字符串进行匹配(假设上面那个串是P，下面那个串是T串)。最开始我们看T的前三个串和P是匹配的，第四个发现不匹配于是我们右移一下 发现不匹配，再右移一步 一直这样直到 于是停止，当然也有可能最后没有对应的匹配串。 代码实现:

import org.junit.Test;public class Main {
       //从P里面找T的匹配串并返回对应索引的位置，如果没有返回-1    int BF(String P,String T){
           int i=0,j=0,current=0;        while(j
   

算法复杂度O((m-n)*n)=O(m*n-n^2)

二.KMP算法

在看KMP算法前我们需要知道为什么需要KMP算法？BF算法他不香吗?

我们先看个例子: 像这样的就会无辜的浪费很多事间去比较。于是KMP就诞生了。

1.prefix table(前缀表)

我们还是来匹配这两个串。 我们看下面的T串"ababc" 他的前缀串为(我们不看他本身)

编号	前缀串
1	a
2	ab
3	aba
4	abab

现在我们需要找到每个前缀串他的前缀与后缀(不考虑串本身)相等的最大长度

于是

前缀串	长度
a	0
ab	0
aba	1
abab	2

接下来就是我们的前缀表:

索引	T串	前后缀相等最大长度
0	a	-1
1	b	0
2	a	0
3	b	1
4	c	2

上面这个前缀表我们可以看成一个数组，取名为Pre;大小为5

那么pre[i]的含义是:

0~(i-1)这i个字符的前后缀相等最大长度，特别的当i=0时我们赋值为-1来区分

2.前缀表的作用

还是前面的P串与T串

最开始从P[0]与T[0]对齐,开始匹配发现P[3]与T[3]不匹配，于是我们看Pre[3]=1，那么就把T[1]与P[3]对齐再来比较: 从新的对齐位置P[3]与T[1]开始往后比较(也即绿线处那里),不匹配，我们看Pre[1]=0,于是我们把T[0]与P[3]对齐 这时从上面的绿线处开始比较，往后比发现T[1]与P[4]不匹配了,这时Pre[1]=0,于是P[4]与T[0]对齐 这时从上面的绿线处开始比较，发现T[0]与P[4]不匹配了,这时Pre[0]=-1,于是P[4]与T[-1]对齐，而实际上T[-1]使我们虚构出来的，实际上是T[0]与P[5]对齐了 这个时候已经匹配上了，当然在这里还没结束，我们确实找到了第一个，但是后面可可能还有，因此下一步我们应该看T匹配完成的最后一个字符即T[4],这里Pre[4]=2,于是我们T[2]与P[9]对齐 这时继续前面的操作，最后到这里才是真正的结束了，现在我们对KMP算法已经了解了

3.代码实现

实际上这里的Pre数组就是我们常说的next数组

import org.junit.Test;/** * @author  jackTan */public class MainTest {
       /**     * 在串P中匹配T串，只匹配第一个，如果没有就返回-1，否则返回匹配到的P中的索引     * @param p     * @param t     * @return     */    int Kmp_Search(String p,String t){
           //第一步获取前缀串        int []pre = getPre(t);        //i指向p串的字符,j指向t串的字符        int i=0,j=0;        while(i
   

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