kMP算法

JAVA数据结构和算法：第五章（串和KMP算法）
2017年08月30日 19:48:34
阅读数：227

串

串是由零个或多个字符组成的有限序列，经常被称为字符串。一般记为s=”a1a2a3a4..an”.

零个字符的串被称为空串，长度为0.

串中任意个数的连续字符组成的序列被称为子串，包含子串的串被称为主串。例如lover是love的主串，love是lover的空串。

串的比较

字符串的比较是通过字符之间的ASCII编码值来确定大小的。比较两个字符串是否相等，必须是它们的长度以及对应位置的字符都相等才认定相等。而大小的比较则是从第一个字符依次比较ASCII值，如果A串中指定位置的字符ASCII值小于B串中对应位置的字符ASCII值，则说明A串 < B串。

java中的String类实现了字符串的各种方法，大家可以去参考，这里就不再来实现，因为蛮简单的。我们主要来讲一个字符串很常用的匹配算法。

朴素模式匹配算法

我们如果要计算一篇英文文章中有多少个某个单词，其实就是子串的定位问题，这种子串的定位操作通常称作串的匹配模式。我们把子串称为模式串。

我们讲个例子，例如要从S=”goodgoogle”字符串中找到”T=google”这个子串的位置.

这里写图片描述

这里写图片描述

这里写图片描述

我们来实现一下这个算法

    public static int getIndex(String s,String t) {
        char[] array1=s.toCharArray();
        char[] array2=t.toCharArray();
        int i=0;
        int j=0;
        //判断字符串长度
        while(i<s.length()&&j<t.length()) { 
            //从第i个下标比
            if(array1[i]==array2[j]) {
                i++;
                j++;
            //如果不一样的话，就从上次开始比较位置的后一位开始比，并且子串从0开始    
            }else { //goodgoogle  google
                i=i-j+1;
                j=0;
            }

        } 
        //判断j是否等于子串的长度，相等即返回在主串中的位置
        if(j>=array2.length) {
            return i-array2.length;
        }
        return -1;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

我们来分析一下算法时间复杂度，如果一开始就匹配成功，时间复杂度为O(1)。 
最坏的情况是什么呢？就是每次不成功的匹配都发生在子串的最后一个字符，例如S=”00000000000000000000000000000000000000000000000001”，要匹配的子串为“0000000001”，这样当匹配时，每次都要匹配到最后一个字符才能发现不匹配。这样等于子串在主串的前40个位置上都需要判断十次，并且还不匹配。因为最坏情况的时间复杂度为O(（主串长度-子串长度+1）* 子串长度).例如这个例子就是O((50-10+1)*10)。由此可见，这种算法效率简直太低下了，我们需要寻找其他的算法。

KMP模式匹配算法

我们的算法效率太过低下，而科学家们明显不能忍受这种情况。于是有三位科学家发表了一种模式匹配算法，简称为KMP算法。

KMP算法原理

如果有一个主串S=”abcdefgab….” 等等很长，我们要匹配的子串为T=”abcdex”，如果用我们朴素模式匹配算法，前面的五个字符完全相同，直到第6个字母不匹配，然后接着从主串的下一个位置开始匹配，这是我们以前的算法，效率很低很低 。

这里写图片描述

我们仔细来分析一下，对于子串“abcdex”来说，它的首字母‘a’不与自己后面的子串中的任一字符相等（很重要的前提，可以预处理先比较自身），然后我们子串的前五位和主串的前五位是相等的，这也就能推出子串的首字母 ‘a’ 不可能和主串的第二到第五位的字符相等，就意味着首字母无需再与第二到第五位判断，而接下来就是直接从主串第六位和子串首字母判断比较，也就省去了很多步骤，注意这里是KMP算法的关键，利用自身已知的一些信息来获得移动的长度。

这里写图片描述

但是也有一些特殊情况需要考虑。如果子串T后面也含有首字母“a”怎么办，也就是后面有重复的字母？假设S=”abcabcabc”，要匹配的子串为T=”abcabx”，根据我们上面推导的，首先首字母无需再和主串第二、三位比较，但我们知道子串首字母和子串的第四位相同，子串的第二个字母和子串的第五位相同，而我们也知道子串的第四和第五位和主串的第四第五位相同，既然这样，子串的首字母和第二个字母也就无需和主串的第四第五位比较，只需要将子串移动到主串的第四位，但是无需再比较前两个，直接从第三个比较。也就是说，对于在子串中有与首字符相等的字符，有时候也可以省去一些不必要的判断步骤。

这里写图片描述

这时候我们就明确了，KMP算法提高效率其实就是确定这次匹配失败后，下次不用再重复的回溯到前面去匹配我们已经知道不可能相同的位置，而是直接跳到某个位置接着进行匹配。KMP算法通过一个“有用信息“，这个“有用信息”就是用所谓的“前缀函数（很多书中提到的的next函数）”来存储的。这个函数能够反映出现失配情况时，系统应该跳过多少无用字符而进行下一次检测。

通过上面分析我们知道，KMP算法最重要的两个难点：

  • 是这个前缀函数的求法。
  • 二是在得到前缀函数之后，怎么运用这个函数所反映的有效信息跳过不必要的判断。

首先我们得明白”前缀”和”后缀”的概念。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。例如”ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D].

我们前面讲过需要对子串自身进行预处理，这样就可以省去很多比较步骤，我们把处理结果保存在一个Next[]数组中。next[i]表示的就是前i个字符组成的这个子串最长的相同前缀后缀的长度。例如字符串aababaaba的相同前缀后缀有a和aaba，那么其中最长的就是aaba，即为4。

那么我们就可以得到子串的Next数组。以“ABCDABD”为例

"A"的前缀和后缀都为空集，共有元素的长度为0；

"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。 

所以next[]="0000120"
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

举个例子：例如主串S=”abcabcdabcdabx”,T=”abcdabx” ,我们先算出T的next数组，next[]=”0000120”

第一步：我们先从0开始匹配，匹配到子串第3位（下标为0开始）不匹配，则计算失配的前一个位置的next值，即next[3-1]=0 
故接下来让子串的0位置和主串的当前位置对齐比较，重点：主串是不变的，因为当前主串的位置是3，所以让子串从0开始和主串当前位置对齐然后比较

abcabcdabcdabx
   abcdabx
  • 1
  • 2
  • 3

第二步接着匹配，匹配到第子串第6位又不匹配，next[6-1]=2，这时我们应该让子串2位置和主串当前位置对齐，然后从2开始比较

abcabcdabcdabx
       abcdabx
  • 1
  • 2
  • 3

接下来完全匹配，返回位置，这样就会发现无用的判断少了很多。

接下来我们来写下代码实现

 public class Test {  

    public static void main(String[] args) {   
        String s="abcabcabcabcabcabcabcabcabx";
        String t="abcabx";
        kmp(s.toCharArray(),t.toCharArray(),new int[t.length()]);

    }   


    //计算next数组
    static  void makeNext(char[] str,int next[])
    {
        int index,biglength;//index:模版字符串下标；biglength:最大前后缀长度
        int len = str.length;//模版字符串长度
        next[0] = 0;//不论如何，模版字符串的第一个字符的最大前后缀长度为0
        for (index = 1,biglength = 0; index < len; ++index)//for循环，从第二个字符开始，依次计算每一个字符对应的next值
        {
            //如果出现最大前后缀长度>0并且最后一个元素不等于str[最大前后缀长度]的情况，那么就说明没有相同的前后缀,即失配，所以我们需要来计算一下当前串的最大前后缀长度，这里大家可以自己用个例子分析一下
             while(biglength > 0 && str[index] != str[biglength])//求P[0]···P[index]的最大的相同的前后缀长度biglength
                 biglength = next[biglength-1];          
             if (str[index] == str[biglength])//如果前后缀单个字符相等，那么最大相同前后缀长度加1
             {
                 biglength++;
             }
             next[index] = biglength;
        }
    } 

    /*计算next数组，这种方式比较简单点
   /*
   static  void makeNext(char[] str,int next[]) {
        int index,biglength;
        next[0]=0;
        for(index =1,biglength=0;index<str.length;index++) {
            if(str[index]!=str[biglength]&&biglength>0) {
                next[index]=0;
            }else {
                next[index]=++biglength;
            }
        }
    }*/  


   //kmp算法，传入主串、模式串和next数组 
  static  int kmp(char T[],char P[],int next[])
    {
       //两个变量
        int i,q;
        //主串的长度和模式串的长度
        int  Tlength = T.length;
        int  Plength = P.length;
        makeNext(P,next);
        for (i = 0,q = 0; i < Tlength; ++i)
        {
            //如果出现字符不相等的情况，则调用next跳到指定位置，从指定位置开始比较
            while(q > 0 && P[q] != T[i])
                q = next[q-1];
            //判断子串的字符是不是和主串都相同
            if (P[q] == T[i])
            {
                q++;
            }
            //如果q等于子串长度，则说明匹配成功
            if (q == Plength)
            {
                System.out.println((i-Plength+1));
            }
        }    

        return 0;
    }


}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75

　　 
KMP算法真的是蛮难理解的一个算法，对初学者来说难度还是蛮大的，不过模式匹配算法比KMP性能好的有很多，可能是因为比较经典，在各大教科书中都有涉及，大家可以慢慢地学习一下。　　 
　　

此文参考的有《大话数据结构》和如下博客，大家可以去看一下

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/jiang--nan/p/9073371.html