数据结构篇——KMP算法

时间:2022-11-19 09:03:50

本次我们介绍数据结构中的KMP算法,我们会从下面几个角度来介绍:

  • 问题介绍
  • 暴力求解
  • 知识补充
  • Next示例
  • Next代码
  • 匹配示例
  • 匹配代码
  • 完整代码

问题介绍

首先我们先介绍适用于KMP算法的问题:

  • 给定一个字符串S,以及一个模式串P,所有字符串中只包含大小写英文字母以及阿拉伯数字。
  • 模式串P在字符串S中多次作为子串出现。
  • 求出模式串P在字符串S中所有出现的位置的起始下标。

我们给出一个问题的简单示例:

// 输入 p长度 p s长度 s
3
aba
5
ababa
    
// 输出结果
0 2

暴力求解

所有问题我们都是在暴力求解的基础上进行更新迭代的,所以我们首先给出暴力求解:

// 下面为伪代码,只是起到思路作用

// 首先我们需要创造s[],p[],并赋值
S[N],P[N]
    
// 然后我们开始匹配,我们会从S的第一个字符开始匹配,设置一个flag判断该字符开始的字符串是否与P字符匹配
// 该算法从每个i开始,全部进行匹配
for(int i = 1;i <= n;i++ ){
    boolean flag = true;
    for(int j = 1;j <= m;j++){
        if(s[i+j-1] != p[j]){
            flag = false;
            break;
        }
    }
}

// 我们给出一套完整的暴力求解方法

/**

 * 暴力破解法

 * @param ts 主串

 * @param ps 模式串

 * @return 如果找到,返回在主串中第一个字符出现的下标,否则为-1

 */

public static int bf(String ts, String ps) {

    char[] t = ts.toCharArray();

    char[] p = ps.toCharArray();

    int i = 0; // 主串的位置

    int j = 0; // 模式串的位置

    while (i < t.length && j < p.length) {

       if (t[i] == p[j]) { 
           
           // 当两个字符相同,就比较下一个
           i++;
           j++;

       } else {

           i = i - j + 1; // 一旦不匹配,i后退(从之前i的下一位开始,也是遍历所有i)

           j = 0; // j归0
       }
    }

    // 当上面循环结束,必定是i到头或者j到头,如果是j到头,则说明存在子串符合父串,我们就将头位置i返回
    if (j == p.length) {
       return i - j;
    } else {
       return -1;
    }

}

// 但是我们会发现:我们可以不让i回退而是让j回退,使j回退到能够与当前i相匹配的点位,然后继续进行主串和模式串的匹配

首先我们会发现这个算法的时间复杂度为O(n^2)

我们其中可以优化的点就是i的位置更新,我们可以根据p字符串的特性来判断i在失败后最近可以移动到哪个点位!

知识补充

我们为了学习KMP算法,我们需要补充一些下面会用到的知识:

  • s[ ]是模式串,即比较长的字符串。
  • p[ ]是模板串,即比较短的字符串。(这样可能不严谨。。。)
  • “非平凡前缀”:指除了最后一个字符以外,一个字符串的全部头部组合。
  • “非平凡后缀”:指除了第一个字符以外,一个字符串的全部尾部组合。(后面会有例子,均简称为前/后缀)
  • “部分匹配值”:前缀和后缀的最长共有元素的长度。
  • next[ ]是“部分匹配值表”,即next数组,它存储的是每一个下标对应的“部分匹配值”,是KMP算法的核心。(后面作详细讲解)。

我们所用到的思想是:

  • 在每次失配时,不是把p串往后移一位,而是把p串往后移动至下一次可以和前面部分匹配的位置,这样就可以跳过大多数的失配步骤
  • 而每次p串移动的步数就是通过查找next[ ]数组确定的

Next示例

我们给出一个简单的Next示例:

// 首先我们给出一个next手写实例

/*
模板串为:ABABAA
    
next[0]代表t[0]-t[0],即"A" , "A"的前缀和后缀都为空集,共有元素的长度为0.

next[1]代表t[0]-t[1],即"AB",前缀为“A”,后缀为“B”,共有元素的长度为0..

next[2]代表t[0]~t[2],即"ABA",前缀为“AB",后缀为"BA",最大前后缀即"A",长度为1.

next[3]代表t[0]~t[3],即"ABAB",前缀为"ABA"后缀为"BAB”,最大前后缀即"AB ",长度为2.

next[4]代表t[0]~t[4],即"ABABA",前缀为"ABAB",后缀为"BABA",最大前后缀即" ABA",长度为3.

next[5]代表t[0]-t[5],即" ABABAA",前缀为“ABABA",T后缀为“BABAA";最大前后缀即"A",长度为1.

*/

// 我们next的作用是使next[j]=k使 P[0 ~ k-1] == P[j-k ~ j-1]、
// 当第n个数不匹配时,我们让j回退到k,这时我们的主串和模式串的前缀还属于匹配状态,我们继续进行匹配
例如 ababc
    我们如果匹配到c不符合时,我们可以使j回退到k(这里的k是2,即a)再继续进行匹配
    因为我们的c前面的ab和开头的ab是匹配的,我们主串中的i前面肯定也是ab,我们的l前面也是ab,所以两者匹配,我们可以继续后面的匹配
    相当于我们的x不变,我们将j放在2的位置,前面的ab已完成匹配,我们只需要匹配abc即可

// 公式书写就是下述:
    
当T[i] != P[j]时

有T[i-j ~ i-1] == P[0 ~ j-1]

由P[0 ~ k-1] == P[j-k ~ j-1]

必然:T[i-k ~ i-1] == P[0 ~ k-1]

Next代码

我们给出求解Next的代码展示:

public static int[] getNext(String ps) {

    char[] p = ps.toCharArray();

    int[] next = new int[p.length];

    // 这里的next[0]需要等于-1
    // 因为j在最左边时,不可能再移动j了,这时候要应该是i指针后移。所以在代码中才会有next[0] = -1;这个初始化。
    next[0] = -1;

    // 这里设置j的初始值从第一个开始(我们需要得到全部next数组)
    int j = 0;

    // 这里设置k,k就是应该返回的位置,也就是我们常说的前缀和后缀匹配区域的前缀的后一个位置
    int k = -1;

    // 进行循环,得到next数组
    while (j < p.length - 1) {

        // 首先是k==-1时,说明前面已无匹配状态,我们重新开始
        // 然后是p[j] == p[k],说明循环时新添加的值,与我们应该返回比对的位置相同
        // 同时由于我们之前的部分都是已经匹配成功的,所以加上这个数使我们的匹配长度又增加一位
       if (k == -1 || p[j] == p[k]) {

           // 当两个字符相等时要跳过(因为p[k]与S[i]不符合的话,由于我们的p[j]=p[k],所以肯定也不符合,我们直接跳下一步)
           if (p[++j] == p[++k]) { 

              next[j] = next[k];

           } else {
			// 因为在P[j]之前已经有P[0 ~ k-1] == p[j-k ~ j-1]。(next[j] == k)
			// 这时候现有P[k] == P[j],我们是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。
       		// 即:P[0 ~ k] == P[j-k ~ j],即next[j+1] == k + 1 == next[j] + 1
            // 前面我们已经进行了j++和k++,所以这里直接赋值即可
              next[j] = k;

           }

       } else {
		// 如果当前状态无法匹配,我们就跳回上一个前缀后缀相同部分再来判断是否前后缀相同
           k = next[k];

       }

    }

    return next;

} 

匹配示例

我们给出简单的匹配示例:

// 匹配相对而言就比较简单了

主串:abababc
模式串:abc
    
我们首先进行i++,j++范围的匹配,当第三位,即a和c匹配不成功时,我们不移动i,而是移动j
我们将j=2,移动到j=0,即next[2]的位置,在之后一直匹配并再对j进行一次移动,到最后匹配成功为止

匹配代码

我们给出对应的匹配代码:

/*该代码实际上是由暴力求解代码改造过来的*/

public static int KMP(String ts, String ps) {

    char[] t = ts.toCharArray();

    char[] p = ps.toCharArray();

    int i = 0; // 主串的位置

    int j = 0; // 模式串的位置

    int[] next = getNext(ps);
    
    // 开始判断(设置边界值)
    while (i < t.length && j < p.length) {

        // 当j为-1时,要移动的是i,当然j也要归0
        // 如果匹配成功,两者都进行移动,开始下一位比对
       if (j == -1 || t[i] == p[j]) { 

           i++;

           j++;

       } else {
		   // 如果比对失败,我们将 j 返回next数组指定位置继续匹配
           
           // i不需要回溯了
           // i = i - j + 1;

           j = next[j]; // j回到指定位置

       }

    }

    // 最后同样进行判断,是否符合条件
    if (j == p.length) {

       return i - j;

    } else {

       return -1;

    }

}

完整代码

最后为大家展示一下完整代码:

import java.util.Scanner;

class ppp {

    /**
     * 主代码
     * @param args
     */
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        String ts = scanner.nextLine();

        String ps = scanner.nextLine();

        int kmp = KMP(ts, ps);

        System.out.println(kmp);
    }

    /**
     * kmp算法
     * @param ts
     * @param ps
     * @return
     */
    public static int KMP(String ts, String ps) {

        char[] t = ts.toCharArray();

        char[] p = ps.toCharArray();

        int i = 0; // 主串的位置

        int j = 0; // 模式串的位置

        int[] next = getNext(ps);

        // 开始判断(设置边界值)
        while (i < t.length && j < p.length) {

            // 当j为-1时,要移动的是i,当然j也要归0
            // 如果匹配成功,两者都进行移动,开始下一位比对
            if (j == -1 || t[i] == p[j]) {

                i++;

                j++;

            } else {
                // 如果比对失败,我们将 j 返回next数组指定位置继续匹配

                // i不需要回溯了
                // i = i - j + 1;

                j = next[j]; // j回到指定位置

            }

        }

        // 最后同样进行判断,是否符合条件
        if (j == p.length) {

            return i - j;

        } else {

            return -1;

        }

    }

    /**
     * next数组求解
     * @param ps
     * @return
     */
    public static int[] getNext(String ps) {

        char[] p = ps.toCharArray();

        int[] next = new int[p.length];

        // 这里的next[0]需要等于-1
        // 因为j在最左边时,不可能再移动j了,这时候要应该是i指针后移。所以在代码中才会有next[0] = -1;这个初始化。
        next[0] = -1;

        // 这里设置j的初始值从第一个开始(我们需要得到全部next数组)
        int j = 0;

        // 这里设置k,k就是应该返回的位置,也就是我们常说的前缀和后缀匹配区域的前缀的后一个位置
        int k = -1;

        // 进行循环,得到next数组
        while (j < p.length - 1) {

            // 首先是k==-1时,说明前面已无匹配状态,我们重新开始
            // 然后是p[j] == p[k],说明循环时新添加的值,与我们应该返回比对的位置相同
            // 同时由于我们之前的部分都是已经匹配成功的,所以加上这个数使我们的匹配长度又增加一位
            if (k == -1 || p[j] == p[k]) {

                // 当两个字符相等时要跳过
                //(因为p[k]与S[i]不符合的话,由于我们的p[j]=p[k],所以肯定也不符合,我们直接跳下一步)
                if (p[++j] == p[++k]) {

                    next[j] = next[k];

                } else {
                    // 因为在P[j]之前已经有P[0 ~ k-1] == p[j-k ~ j-1]。(next[j] == k)
                    // 这时候现有P[k] == P[j],我们是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。
                    // 即:P[0 ~ k] == P[j-k ~ j],即next[j+1] == k + 1 == next[j] + 1
                    // 前面我们已经进行了j++和k++,所以这里直接赋值即可
                    next[j] = k;

                }

            } else {
                // 如果当前状态无法匹配,我们就跳回上一个前缀后缀相同部分再来判断是否前后缀相同
                k = next[k];

            }

        }

        return next;

    }
}

结束语

好的,关于数据结构篇的KMP算法就介绍到这里,希望能为你带来帮助~