首页 » Java » 字符串匹配-KMP算法 讲解与java代码实现

字符串匹配-KMP算法 讲解与java代码实现

原文 http://blog.csdn.net/bury_/article/details/79199228

2018-01-30 02:00:40阅读(421)

如何高效地查找字符串a是否包含字符串s?

可以使用KMP算法,首先计算字符串s的模式偏移数组next,然后在遍历a查找s的时候可以利用next偏移数组对s进行偏移,以求更快地进行匹配检测。

假设要计算字符串a=”bcbcbacbcbcbc”是否包含字符串s=”bcbcbc”。

1.算法思想

第一步:计算字符串”bcbcbc”的next偏移数组:
字符串匹配-KMP算法 讲解与<a href=java代码实现" src="http://img.blog.csdn.net/20180129192556259?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYnVyeV8=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="这里写图片描述" title="">

next[0]=-1,next[1]=-1,next[2]=0,next[3]=1,next[4]=2,next[5]=3

next[i]表示的是字符串 s 从位置 0 到位置 i 构成的子串 p 的最长前缀的长度减去 1 的值。 这
里最长前缀需要满足两个要求,一是其长度最大为子串 p 长度减去 1,也就是小于 p,不能等于p;二是它必须等于最长后缀。

比如,字符串 s 的子串 “b” 没有最长前缀,因为不满足第一条;子串 “bc”
没有最长前缀,因为不满足第二条,即其最长前缀 b 不等于最长后缀 c;”bcb” 的最长前缀为b。

第二步:遍历字符串a,检测是否包含字符串s,同时利用next数组对s进行偏移:
字符串匹配-KMP算法 讲解与java代码实现
i 是字符串 a 的索引, i 从位置 0 遍历到位置 5,依次和字符串 s 相应位置上的字符进行比较;当i 遍历到 位置5 时(图中橘色位置),两个字符串上的字符不匹配,(a!=c), 如果没有 next 偏移数组,我们可以又从子串 s 的第 0 号位置和 a 的第 5 号位置开始比较;但是有了 next 偏移数组,我们就可以充分利用已经比较过的字符,知道该从子串的哪个位置开始继续和 a 进行比较。因为 next[4]等于 2,那么我们直接比较a[5]和s[2+1]即s[3]
字符串匹配-KMP算法 讲解与java代码实现
此时发现a[5]和s[2+1]即s[3]仍然不匹配,由于next[2]为0,那么我们比较a[5]和s[0+1],即比较a[5]和s[1]
字符串匹配-KMP算法 讲解与java代码实现
仍然不匹配,由于next[0]为-1,则比较a[5]和s[-1+1]即比较a[5]和s[0],还是不匹配,(a!=b),此时子串s已经回溯到了0号位置,则a向后遍历,比较a[6]和s[0],不匹配(c!=b)
字符串匹配-KMP算法 讲解与java代码实现
比较a[7]和s[0],直到a遍历到了最后位置12,此时s的指针k也刚好遍历到了最后的5号位置,则说明字符串a有匹配s的位置。
字符串匹配-KMP算法 讲解与java代码实现

2.JAVA实现:

KMP检测str是否包含字符串ptr:

//str是待检测字符串,ptr是搜索的模式子串
    public boolean KMP(char[] str,char[] ptr){
        //计算模式子串的next数组
        int[] next=cal_next(ptr);
        int slen=str.length;
        int plen=ptr.length;//子串的长度
        int j=-1;
        for(int i=0;i<slen;i++){
            while(j>-1&&ptr[j+1]!=str[i]){
                j=next[j];
            }
            if(ptr[j+1]==str[i]){
                j=j+1;
            }
            //模式子串遍历到了最后,则说明匹配成功
            if(j==(plen-1)){
                return true;
            }
        }
        return false;
    }

计算ptr的next数组:

 public int[] cal_next(char[] s){
        int len=s.length;
        int[] next=new int[len];
        next[0]=-1;
        int k=-1;//k表示s[0,k]字符串的最长前缀等于最长后缀时的最长前缀长度减去1
        //遍历长度为n的子串,时间复杂度O(n)
        for(int q=1;q<=(len-1);q++){
            //如果下一个不同,那么k就变成next[k],注意next[k]是小于k的,无论k取任何值。
            while(k>-1&&s[k+1]!=s[q]){
                k=next[k];//往前回溯
            }
            if(s[k+1]==s[q]){
                k=k+1;
            }
            //这个是把算的k的值(就是相同的最大前缀或最大后缀的长度减去1)赋给next[q]
            next[q]=k;
        }
        return next;
    }
3.参考:

《算法导论》32章字符串匹配-KMP算法

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹