KMP算法

type

Post

status

Published

date

Jul 27, 2022

slug

KMP

summary

考研复习时，自己对于串匹配算法，KMP算法的理解，感觉仍有待提高

参考资料

漫画：什么是KMP算法？

在字符串匹配算法的前两讲，我们分别介绍了暴力算法BF算法，利用哈希值进行比较的RK算法，以及尽量减少比较次数的BM算法，没看过的小伙伴可以点击下方链接：如果没时间细看也没关系，就让我带着大家简单梳理一下。正如同它的全称BruteForce一样，BF算法使用简单粗暴的方式，对主串和模式串进行逐个字符的比较： ...

https://baijiahao.baidu.com/s?id=1659735837100760934&wfr=spider&for=pc

研究背景

专业课复习KMP算法时，发觉自己比赛后，时日过长对于KMP算法已经遗忘过多

趁此机会捞一下自己

手推了不少算法流程，受益颇多

对于暴力匹配时，在移动串位置时，移动速度不够优秀

提出KMP算法，实现了利用已经部分匹配这个有效信息

保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置

算法描述

第一轮，模式串和主串的第一个等长子串比较，发现前5个字符都是匹配的，第6个字符不匹配

在下一轮的比较时，只有把这两个相同的片段对齐，才有可能出现匹配

这两个字符串片段，分别叫做最长可匹配前缀子串和最长可匹配后缀子串。

直接把模式串向后移动两位，让两个“GTG”对齐，继续从刚才主串的不匹配字符A开始进行比较

这样就可以降低匹配的复杂度

而如何寻找最长可匹配后缀子串和最长可匹配前缀子串，就成了重要问题

next数组

通常对于这个可以支持模式串进行滑动的数组称为next数组

在数据结构书中存在以下对next数组的定义

步骤如下

比较每个元素之前的前缀和后缀是否相等

注意字符串比较相等要正着看，而不是看成回文字符串

next[]=0用于后续代码里方便前移操作

同时注意是比较当前结点之前的元素，不包括当前结点

此next数组对以下标1开始的匹配串生效

而利用next匹配的过程示例如下

KMP整体代码算法


public int KMP(int s[],int v[],int next[],int pos){
        int i = pos,j=0;
        while(i<s.length && j<v.length)
        {
            if( j==-1 || s[i] == v[j]) {++i;++j;}
            else j = next[j];
        }
        if(j>=v.length)return i;//此处返回匹配后的下标
        else return -1;
    }

算法复杂度

next函数求解代码

书中对于概念上的深入解析

其本质在于

对于最开始的next[1]赋值为0，作为一个都匹配不到时的空

对于执行过程中，若前后缀相同，各自进位，并记录下此时的next值

对于执行过程中，前后缀不同，将问题递归看待为新的模式匹配问题，去求这个的最优前后缀，所以j=next[j] 这样更快的找到新的模式串

图解步骤


public int[] get_next(int s[]){
        int[] next = new int[s.length];
        int i=0;
        int j=-1;
        next[i]=-1;
        while(i<s.length-1){
            if(j==-1 || s[i]==s[j]){++i;++j;next[i]=j;}
            else j = next[j];
        }
        return next;
    }

算法复杂度

next函数修正值

对于next存在一个问题，如果有多个连续的相同元素，回退时会一步步的回退，而不会直接回到最开始的首个元素，这样会比较耗时

所以对于多个相同元素，我们将其一步到位，指向最开始元素的位置


public int[] get_nextval(int s[],int next[])
    {
        int[] nextval = new int[s.length];
        int i=0,j=-1;
        nextval[0]=-1;
        while(i<s.length-1){
            if(j==-1 || s[i]==s[j]){
                ++i;++j;
                if(s[i] != s[j])nextval[i]=j;
                else nextval[i] = nextval[j];
            }
            else j = nextval[j];
        }
        return nextval;
    }