kmp算法字符串匹配算法

简介

字符串模式匹配是对字符串的基本操作之一,广泛应用于生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等领域,如何简化其复杂性一直是算法研究中的经典问题。字符串的模式匹配实质上就是寻找模式串P是否在主串T 中,且其出现的位置。我们对字符串匹配的效率的要求越来越高, 应不断地改良模式匹配算法,减少其时间复杂度。

算法说明

设主串(下文中我们称作T)为:a b a c a a b a c a b a c a b a a b b
模式串(下文中我们称作W)为:a b a c a b
用暴力算法匹配字符串过程中,我们会把T[0] 跟 W[0] 匹配,如果相同则匹配下一个字符,直到出现不相同的情况,此时我们会丢弃前面的匹配信息,然后把T[1] 跟 W[0]匹配,循环进行,直到主串结束,或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法,极大地降低了匹配效率。
而在KMP算法中,对于每一个模式串我们会事先计算出模式串的内部匹配信息,在匹配失败时最大的移动模式串,以减少匹配次数。
比如,在简单的一次匹配失败后,我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的:在已经匹配的模式串子串中,找出最长的相同的前缀后缀,然后移动使它们重叠。
在第一次匹配过程中
T: a b a c a a b a c a b a c a b a a b b
W: a b a c a b
在T[5]与W[5]出现了不匹配,而T[0]~T[4]是匹配的,其中T[0]~T[4]就是上文中说的已经匹配的模式串子串,移动找出最长的相同的前缀和后缀并使他们重叠:
T: a b a c aa b a c a b a c a b a a b b
W: a b a c a b
然后在从上次匹配失败的地方进行匹配,这样就减少了匹配次数,增加了效率。
然而,如果每次都要计算最长的相同的前缀反而会浪费时间,所以对于模式串来说,我们会提前计算出每个匹配失败的位置应该移动的距离,花费的时间就成了常数时间。比如:
j012345
W[j]abacab
F(j)001011
当W[j]与T[j]不匹配的时候,设置j = F(j-1).
朱洪对KMP算法作了修改,他修改了KMP算法中的next函数,即求next函数时不但要求W[1,next(j)-1]=W[j-(next(j)-1),j-1],而且要求W[next(j)]<>W[j],他记修改后的next函数为newnext。显然在模式串字符重复高的情况下,朱洪的KMP算法比KMP算法更加有效。
假设在执行正文中自位置 i 起“返前”的一段与模式的自右至左的匹配检查中,一旦发现不匹配(不管在什么位置),则去执行由W[m]与t[i]+d(x)起始的自右至左的匹配检查,这里x是字符t。它的效果相当于把模式向右滑过d(ti)一段距离。显然,若ti不在模式中出现或仅仅在模式末端出现,则模式向右滑过的最大的一段距离m。图1.1示出了执行BM算法时的各种情况。实线连接发现不匹配以后要进行比较的正文和模式中的字母,虚线连接BM算法在模式向右滑后正文和模式中应对齐的字母,星号表示正文中的一个字母。
public class StringMatching {
    public static void main(String[] args) {
        //暴力匹配算法
        String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
        String str2 = "尚硅谷你尚硅你";
        int match = violenceMatch(str1, str2);
       // System.out.println(match);

        String s1= "BBC ABCDAB ABCDABCDABDE";
        String s2 = "ABCDABD";
        String s3 = "ABC";
        int[] next = kmpNext("ABCDABD");//[0,1]
        int res = kMP(s1, s2, next);
        System.out.println(Arrays.toString(next));
        System.out.println(res);

    }


    /*暴力匹配算法*/
    public  static  int violenceMatch(String str1,String str2){
      char[] s1 = str1.toCharArray();
      char[] s2 = str2.toCharArray();
      int i=0;//索引指向s1
      int j = 0;//索引指向s2
        while (i<s1.length&&j<s2.length){//匹配不越界
            if (s1[i] ==s2[j]){//匹配成功
               i++;
               j++;
            }else {//不成功
                i = i -(j-1);
                j=0;
            }
        }
        //判断是否匹配成功
        if (j==s2.length){
            return  i-j;
        }else {
            return -1;
        }
    }

   /*获取到一个字符串的部分匹配值*/
    public static  int[] kmpNext(String dest){
        /*保存部分匹配值*/
        int[] next = new int[dest.length()];
        next[0] = 0;//如果字符串长度为1;部分匹配值是0;
        for (int i = 1 ,j=0; i <dest.length() ; i++) {
            //当不相等时需要从j-1获取新的j
            /*直到发现dest.charAt(i) == dest.charAt(j)退出*/
               while (j>0 &dest.charAt(i) != dest.charAt(j)){
                   j=next[j-1];//kmp算法的基础
               }
        if (dest.charAt(i) == dest.charAt(j)){
            j++;
        }
        next[i] =j;
        }
        return next;
    }

    /*KMP算法查找字符最早出现的位置*/
    public  static  int kMP(String str1,String str2,int[] next){
        for (int i = 0 ,j=0; i <str1.length() ; i++) {

            /*需要考虑str1.charAt(i) !=str2.charAt(j)时*/
            while (j>0&&str1.charAt(i)!=str2.charAt(j)){
                j=next[j-1];
            }

            if (str1.charAt(i) ==str2.charAt(j)){
                j++;
            }
            if (j==str2.length()){
                return i - j + 1;
            }
        }
        return -1;
    }

}

相关推荐