作者：whisper

链接：http://proprogrammar.com:443/article/423

声明：请尊重原作者的劳动，如需转载请注明出处

    刚又学了一下KMP算法，虽然精髓的东西还是掌握不了，但代码还是记下来了，可以简单使用了，下面就来分享一下我学习的内容。

    KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

    字符串匹配中有两个字符串，一个是原串，一个是子串（也称模式串），匹配即是从原串中找模式串（的位置）

    通常的匹配算法在与模式串匹配失败后，原串移动到下一位再次与模式串进行匹配，如下图

    这种匹配算法在不匹配的情况下会移动原串到下一个位置，但效率较低。KMP算法与这种算法不同，在出现不匹配的情况下会移动模式串到先前的位置，那么模式串移动的规则是怎么样的呢？这里就要介绍一下next数组，模式串移动的位置由next数组确定（注：下图有两个错误，next数组的第二个元素应为0，原串匹配位置不变，描述有问题）

    next数组的值是模式串当前位置之前前缀与后缀相等的最大长度，还是以一张图来说明

    有了上面的知识就可以来看代码的实现了

    // 求next数组
    public void initNext(String p, int[] next) {
		int i = -1, j = 0;
		
		next[0] = -1;
		while(j < p.length() - 1) {
			if(i == -1 || p.charAt(i) == p.charAt(j)) {
				i++;
				j++;
				next[j] = i;
			}else {
				i = next[i];
			}
		}
	}
	
    // 求子串位置
	public int kmp(String s, String p) {
		int[] next = new int[p.length()];
		int i = 0, j = 0;
		
		initNext(p, next);
		
		while(i < s.length() && j < p.length()) {
			if(j == -1 || s.charAt(i) == p.charAt(j)) {
				i++;
				j++;
			}else {
				j = next[j];
			}
		}
		
		if(j == p.length()) {
			return i - j;
		}
		
		return -1;
	}

    求next数组有一个可以优化的地方，看下图

     所以真正的next数组是这样的

    这样我们可以优化获取next数组的代码如下：

    // 求next数组
    public void initNext(String p, int[] next) {
        int i = -1, j = 0;
		
		next[0] = -1;
		while(j < p.length() - 1) {
			if(i == -1 || p.charAt(i) == p.charAt(j)) {
				i++;
				j++;
				
				if(p.charAt(i) == p.charAt(j)){
					next[j] = next[i];
                }else {
                	next[j] = i;
                }
				
			}else {
				i = next[i];
			}
		}
	}

亲爱的读者：有时间可以点赞评论一下