通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

算法学习之KMP算法

10110人浏览 / 1人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  这些算法有自己的方法  | 

作者:因情语写

链接:https://qingyu.blue/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];
            }
        }
    }

 


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

点赞(36) 打赏

全部评论

2020-03-04 20:57
广告位-帮帮忙点下广告