大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

--喜欢记得关注我哟【shoshana】--

大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

目录

1.朴素的模式匹配算法
2.KMP模式匹配算法
  2.1 KMP模式匹配算法的主体思路
  2.2 next[]的定义与求解
  2.3 KMP完整代码
  2.4 一道题目
3.KMP模式匹配算法改进

4.朴素算法和KMP算法的时间复杂度分析

5.KMP算法next[]数组理解
附:

正文

字符串匹配

给你两个字符串,寻找其中一个字符串是否包含另一个字符串,如果包含,返回包含的起始位置。
如下面两个字符串:

string s = "bacbababadababacambabacaddababacasdsd";
string t = "ababaca";

s有两处包含t
分别在s的下标10,26处包含ptr。

“bacbababadababacambabacaddababacasdsd”;

大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

问题类型很简单,下面直接介绍算法

Java版的串的朴素模式匹配算法、KMP模式匹配算法、KMP模式匹配算法的改进算法

1.朴素的模式匹配算法

  为主串和子串分别定义指针i,j。

    (1)当 i 和 j 位置上的字母相同时,两个指针都指向下一个位置继续比较;

    (2)当 i 和 j 位置上的字母不同时,i 退回上次匹配首位的下一位,j 则返回子串的首位。

大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)
(注:该图从下标为1开始 )

  实现程序:

/**
* 朴素的模式匹配算法
* 说明:下标从0开始,与书稍有不同,但原理一样
*/
public class BruteForce { int index(String s, String t, int pos) {
int i = pos;
int j = 0;
while (i < s.length() && j < toString().length()) {
if (s.charAt(i) == t.charAt(j)) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j == t.length()) {
return i - j;
} else {
return -1;
} } public static void main(String[] args) {
BruteForce sample = new BruteForce();
int idx = sample.index("goodgoogle", "google", 0);
System.out.println(idx);
}
}

  

4
4

2.KMP模式匹配算法

2.1 KMP模式匹配算法的主体思路

  大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

  在上图的比较中,当 i 和 j 等于5时,两字符不匹配。在朴素匹配算法中,会令i=1,j=0,然后进行下一步比较;但是,我们其实已经知道了i=1到4的主串情况了,没有必要重复进行i=2到4的比较,且我们观察ABCABB”B前面的ABCAB,其前缀与后缀(黄色部分)相同,所以可以直接进行上图中的第三步比较(令 i 不变,令 j 从5变成2,继续进行比较)。这就是KMP模式匹配算法的大概思路。这当中的 j 从5跳转到了2,2通过一个函数next(5)求得,next(5)即代表j=5位置不匹配时要跳转的下一个进行比较的位置。

  KMP模式匹配算法:

  为主串和子串分别定义指针 i 和 j 。

  (1)当 i 和 j 位置上的字母相同时,两个指针都指向下一个位置继续比较;

  (2)当 i 和 j 位置上的字母不同时,i 不变,j 则返回到next[j]位置重新比较。(暂时先不管next[]的求法,只要记得定义有next[0]=-1)

  (3)当 j 返回到下标为0时,若当 i 和 j 位置上的字母仍然不同,根据(2),有 j = next[0]=-1,这时只能令 i 和 j 都继续往后移一位进行比较 (同步骤(1))。

  上述内容可结合下图说明:

大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

  (1)i 和 j 从下标为0开始比较,该位置两字母相同,i 和 j 往后移继续比较;

  (2)一直比较到 i 和 j 等于5时,两字母不同, i 不变,j 返回到 next[j]的位置重新比较,该子串的next[5]=2,所以 j 返回到下标为2的位置继续与 i=5的主串字母比较。

  (3)在下图情况下,当j=0时,两字母不同,子串只能与主串的下一个元素比较了(即i=1与j=0比较)。根据(2),会使 j=next[j]=next[0]=-1,所以现在的i=0,j=next[0]=-1了,要下一步比较的话两个指针都要加一。

大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法) 大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法) 大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

   根据上述说明可以写出如下代码(代码中的next[]暂时假设已知,之后会讲):

/*
 * 返回子串t在主串s中第pos个字符后的位置(包含pos位置)。若不存在返回-1
 */
public int index_KMP(String s, String t, int pos) {
    int i = pos;  //主串的指针
    int j = 0;  //子串的指针
    int[] next = getNext(t);  //获取子串的next数组
    while (i < s.length() && j < t.length()) {
        if (j == -1 || s.charAt(i) == t.charAt(j)) {
        // j==-1说明了子串首位也不匹配,它是由上一步j=next[0]=-1得到的。
            i++;
            j++;
        else {
            j = next[j];
        }
    }
    if (j == t.length())
        return i - j;
    return -1;
}

  

2.2 next[]的定义与求解

  根据上述内容可知,next[j] 的含义为:当下标为 j 的元素在不匹配时,j 要跳转的下一个位置下标。

  继续结合下图说明:

大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

  当j=5时,元素不匹配,j跳转到next[5]=2的位置重新比较。

  那为什么next[5]的值为2呢?即,为什么j=5不匹配时要跳转到2位置呢?

  观察 ABCABB 这个字符串,下标为5的字符为B,它前面的字符 ABCAB 与主串完全相同,而ABCAB的前缀与后缀(黄色部分)相同,,所以前缀AB不用再进行比较了,直接比较C这个字符,即下标为2的字符,所以next[5]=2。

  那么该如何求解跳转位置next[]呢?通过刚才的讨论,我们可以发现next[j]的值等于 j 位置前面字符串的相同前后缀的最大长度,上面例子就是等于AB的长度2。

  next[]的公式如下:

  

大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

  公式说明:

    1.在j=0时,0位置之前没有字符串,next[0]定义为-1 ;

    2. 在 j 位置之前的字符串中,如果有出现前后缀相等的情况,令 j 变为相等部分的最大长度,即刚刚所说的相同前后缀的最大长度。如上述的ABCABB字符串中,j=5时,前面相等部分AB长度为2,所以next[5]=2;

    3.其余情况下,next[j]=0。其他情况,没有出现字符的前后缀相等,相同前后缀的最大长度自然就是0。

  那求解next[]的代码如何实现呢?以下是代码的分析过程:

    1.定义两个指针 i=0 和 j=-1,分别指向前缀和后缀( j 值始终要比 i 值小),用于确定相同前后缀的最大长度;(因为 i 是后缀,所以我们求的都是 i+1位置的next值next[i+1])

    2.根据定义有:next[0]=-1;

    3.当前缀中 j 位置的字符和后缀中 i 位置的字符相等时,说明 i+1 位置的next值为 j+1 (因为 j+1 为相同前后缀的最大长度,可结合下面两种情况思考)(即next[i+1]=j+1 )

大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法) 大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

    4.j==-1时,说明前缀没有与后缀相同的地方,最大长度为0,则 i+1 位置的next值只能为0,此时也可以表示为next[i+1]=j+1

    5.当 j 位置的字符和 i 位置的字符不相等时,说明前缀在第 j 个位置无法与后缀匹配,令 j 跳转到下一个匹配的位置,即 j= next[j] 。

  以下是实现求解next[]的程序:

/*
 * 返回字符串的next数组
 */
public int[] getNext(String str) {
    int length = str.length();
    int[] next = new int[length]; //别忘了初始化
    int i = 0;   //i为后缀的指针
    int j = -1;  //j为前缀的指针
    next[0] = -1;
    while (i < length - 1) {         // 因为后面有next[i++],所以不是i<length
        if (j == -1 || str.charAt(i) == str.charAt(j)) { // j == -1代表前后缀没有相等的部分,i+1位置的next值为0          
            next[++i] = ++j;  //等于前缀的长度
        else {
            j = next[j];
        }
    }
    return next;
}

  

2.3 KMP完整代码

  结合next数组的求解和KMP算法,完整代码如下:

  

import java.util.Arrays;
 
/**
 * KMP模式匹配算法
 * 返回子串t在主串s中第pos个字符后的位置。若不存在返回-1 要注意i不变,只改变j
 *
 *
 */
public class KMP {
    /*
     * 返回字符串的next数组
     */
    public int[] getNext(String str) {
        int length = str.length();
        int[] next = new int[length];  //别忘了初始化
        int i = 0;   //i为后缀的指针
        int j = -1;  //j为前缀的指针
        next[0] = -1;
        while (i < length - 1) {         // 因为后面有next[i++],所以不是i<length
            if (j == -1 || str.charAt(i) == str.charAt(j)) { // j == -1代表前后缀没有相等的部分,i+1位置的next值为0          
                next[++i] = ++j;  //等于前缀的长度
            else {
                j = next[j];
            }
        }
        return next;
    }
 
    /*
     * 返回子串t在主串s中第pos个字符后的位置(包含pos位置)。若不存在返回-1
     */
    public int index_KMP(String s, String t, int pos) {
        int i = pos;  //主串的指针
        int j = 0;    //子串的指针
        int[] next = getNext(t);  //获取子串的next数组
        while (i < s.length() && j < t.length()) {
            if (j == -1 || s.charAt(i) == t.charAt(j)) {
            // j==-1说明了子串首位也不匹配,它是由j=next[0]=-1得到的。
                i++;
                j++;
            else {
                j = next[j];
            }
        }
        if (j == t.length())
            return i - j;
        return -1;
    }
 
    public static void main(String[] args) {
        KMP aKmp = new KMP();
        System.out.println(Arrays.toString(aKmp.getNext("BBC")));
        System.out.println(Arrays.toString(aKmp.getNext("ABDABC")));
        System.out.println(Arrays.toString(aKmp.getNext("ababaaaba")));    
        System.out.println(aKmp.index_KMP("goodgoogle""google"0));
    }
}

  

[-1, 0, 1]
[-1, 0, 0, 0, 1, 2]
[-1, 0, 0, 1, 2, 3, 1, 1, 2]
4

2.4 一道题目

已知字符串S为abaabaabacacaabaabcc,模式串P为abaabc。采用KMP算法进行匹配,第一次出现“失配”(S[i]≠P[j])时,i=j=5,则下次开始匹配时,i和j的值分别是:C。
A. i = 1, j = 0
B. i = 5, j = 0
C.i = 5, j = 2
D. i = 6, j = 2

  分析:模式串就是之前所说的子串,i 和 j 是之前所说的指针。根据刚刚的分析中,出现失配时,指针 i 是不会变动的,只会变 j,j=next[j]。next[j]的物理意义是 j 位置前面字符串的相同前后缀的最大长度,我们可以发现abaabcc前面的字符串中相同前后缀为ab,长度为2,所以直接可以选出答案为C。

3.KMP模式匹配算法改进

  对于如下字符串,j=3时,next[j]=1,根据next的定义,即当 j=3位置不匹配时,j跳转到1位置重新比较,但可以发现,j=2位置和j=1位置其实是同一个字母,没有必要重复比较。

大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

  举个例子,在KMP算法下的比较过程如下(按图依次进行):

  大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法) 大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法) 大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

  因为有next[3]=1,所以会出现中间这个其实可以省略掉的过程。实际上我们是可以直接跳到j=0那一步进行比较的,这就需要修改next数组,我们把新的数组记为nextval数组。

  中间那步可以省略是因为,j=3和 j=1位置上的字符是完全相同的,因此没有必要再进行比较了。因此只需要在原有的next程序中加上一个字符是否相等的判断,如果要跳转的nextval位置上的字符于当前字符相等,令当前字符的nextval值等于要跳转位置上的nextval值。

大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

  KMP模式匹配算法的改进程序如下:

import java.util.Arrays;
 
/**
 * KMP模式匹配算法 的改进算法
 * 返回子串t在主串s中第pos个字符后的位置。若不存在返回-1 要注意i不变,只改变j
 *
 */
public class KMP2 {
    /*
     * 返回字符串的next数组
     */
    public int[] getNextval(String str) {
        int length = str.length();
        int[] nextval = new int[length];
        int i = 0;   //i为后缀的指针
        int j = -1;  //j为前缀的指针
        nextval[0] = -1;
        while (i < length - 1) {        
            if (j == -1 || str.charAt(i) == str.charAt(j)) {   
                i++;
                j++;
                if(str.charAt(i)!=str.charAt(j)) { //多了一个字符是否相等的判断
                    nextval[i] = j;  //等于前缀的长度
                }else {
                    nextval[i]=nextval[j];   
                }  
            else {
                j = nextval[j];
            }
        }
        return nextval;
    }
 
    /*
     * 返回子串t在主串s中第pos个字符后的位置(包含pos位置)。若不存在返回-1
     */
    public int index_KMP(String s, String t, int pos) {
        int i = pos;  //主串的指针
        int j = 0;  //子串的指针
        int[] next = getNextval(t);  //获取子串的next数组
        while (i < s.length() && j < t.length()) {
            if (j == -1 || s.charAt(i) == t.charAt(j)) {
            // j==-1说明了子串首位也不匹配,它是由j=next[0]=-1得到的。
                i++;
                j++;
            else {
                j = next[j];
            }
        }
        if (j == t.length())
            return i - j;
        return -1;
    }
 
    public static void main(String[] args) {
        KMP2 aKmp = new KMP2();
        System.out.println(Arrays.toString(aKmp.getNextval("BBC")));
        System.out.println(Arrays.toString(aKmp.getNextval("ABDABC")));
        System.out.println(Arrays.toString(aKmp.getNextval("ababaaaba")));     
        System.out.println(aKmp.index_KMP("goodgoogle""google"0));
    }
}

  

[-1, 0, 1]
[-1, 0, 0, 0, 1, 2]
[-1, 0, 0, 1, 2, 3, 1, 1, 2]
4
[-1, -1, 1]
[-1, 0, 0, -1, 0, 2]
[-1, 0, -1, 0, -1, 3, 1, 0, -1]
4

  改进的算法仅在第24到28行代码发生了改变。

大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

  图中这句话可以结合下表仔细体会。(要记得nextval[j]的含义:j位置的字符未匹配时要跳转的下一个位置)

大话数据结构(8) 串的模式匹配算法(朴素、KMP、改进算法)

4.朴素算法和KMP算法的时间复杂度分析

目标串s (长度m)子串t(长度n )

朴素匹配算法时间复杂度:o(m*n)

KMP算法时间复杂度:o(m+n)

KMP算法 为何简化了时间复杂度:

充分利用了目标字符串s的性质(比如里

面部分字符串的重复性,即使不存在重复字段,在比较时,实现最大的移动量)。

5.KMP算法next[]数组理解

KMP算法用到了next数组,然后利用next数组的值来提高匹配速度,我首先讲一下next数组怎么求,之后再讲匹配方式。

next数组详解

定义一串字符串

ptr = "ababaaababaa";

next[i](i从1开始算)代表着,除去第i个数,在一个字符串里面从第一个数到第(i-1)字符串前缀与后缀最长重复的个数

什么是前缀?

在“aba”中,前缀就是“ab”,除去最后一个字符的剩余字符串。

同理可以理解后缀。除去第一个字符的后面全部的字符串。

在“aba”中,前缀是“ab”,后缀是“ba”,那么两者最长的子串就是“a”;

在“ababa”中,前缀是“abab”,后缀是“baba”,二者最长重复子串是“aba”;

在“abcabcdabc”中,前缀是“abcabcdab”,后缀是“bcabcdabc”,二者最长重复的子串是“abc”;

这里有一点要注意,前缀必须要从头开始算,后缀要从最后一个数开始算,中间截一段相同字符串是不行的。

再回到next[i]的定义,对于字符串ptr = "ababaaababaa";

next[0] = -1 初始值

next[1] = 0,代表着除了第一个元素,之前前缀后缀最长的重复子串,这里是空 ,即"",没有,我们记为-1,代表空。(0代表1位相同,1代表两位相同,依次累加)。

next[2] = 0,即“a”,没有前缀与后缀,故最长重复的子串是空,值为-1;

next[3] = 0,即“ab”,前缀是“a”,后缀是“b”,最长重复的子串“”;

next[4] = 1,即"aba",前缀是“ab”,后缀是“ba”,最长重复的子串“a”;next数组里面就是最长重复子串字符串的个数

next[5] = 2,即"abab",前缀是“aba”,后缀是“bab”,最长重复的子串“ab”;

next[6] = 3,即"ababa",前缀是“abab”,后缀是“baba”,最长重复的子串“aba”;

next[7] = 1,即"ababaa",前缀是“ababa”,后缀是“babaa”,最长重复的子串“a”;

next[8] = 1,即"ababaaa",前缀是“ababaa”,后缀是“babaaa”,最长重复的子串“a”;

next[9] = 2,即"ababaaab",前缀是“ababaaa”,后缀是“babaaab”,最长重复的子串“ab”;

next[10] = 3,即"ababaaaba",前缀是“ababaaab”,后缀是“babaaaba”,最长重复的子串“aba”;

next[11] = 4,即"ababaaabab",前缀是“ababaaaba”,后缀是“babaaabab”,最长重复的子串“abab”;

next[12] = 5,即"ababaaababa",前缀是“ababaaabab”,后缀是“babaaaababa”,最长重复的子串“ababa”;

推荐阅读:
  从头到尾彻底理解KMP(2014年8月22日版)

  字符串匹配的KMP算法

  超详细理解:kmp算法next数组求解过程和回溯的含义

附:

    要记住上面的算法,一定要记住指针 i 和 j 代表的意义,j==-1的意义,以及next的意义。

    (getNext()中前缀位置和后缀位置,index_KMP()中主串位置和子串位置),(前缀或子串的首个字符就无法匹配),(要跳转的下一个位置)

         还有要注意的就是,i为后缀,我们求的是下一个位置的next值,即next[i+1]。

上一篇:我的EF功能


下一篇:戏说PHP的嵌套函数