BF算法和KMP算法

什么是串

数据结构中，字符串要单独用一种存储结构来存储，称为串存储结构。这里的串指的就是字符串。字符串通常是由零个或多个字符组成的有限序列。

一般地，由n个字符串构成的串记作: S=”a0a1……an-1″(n≥0)，串中的ai（1≤i≤n）

• n是一个有限的数值
• 串一般记为S是串的名称，用双引号或单引号括起来的字符序列是串的值（引号不属于串的内容）
• 可以是字母、数字或其他字符，i就是该字符在串中的位置。串中的字符数目n称为串的长度，n是一个有限的数值

无论学习哪种编程语言，操作最多的总是字符串。数据结构中，根据串中存储字符的数量及特点，对一些特殊的串进行了命名，如下：

• 空串：存储 0 个字符的串，例如 S = “”（双引号紧挨着）
• 空格串：只包含空格字符的串，例如 S = ” “（双引号包含 5 个空格）
• 主串和子串：假设有两个串 A 和 B，如果 B 中可以找到几个连续字符组成的串与 A 完全相同，则称 A 是 B 的主串，B 是 A 的子串。例如，若 A = “ZIHUCHUAN”，B = “HUA”，由于 A 中也包含 “HUA”，因此串 A 和串 B 是主串和子串的关系
• 前缀（prefix）、真前缀（proper prefix）、后缀（suffix）、真后缀（proper suffix），真前（后）缀就是指不包含自身的前（后） 如给定一个字符串 string，则：

判断两个串之间是否具有 主串和子串的关系，主要匹配算法有以下两种：

• 朴素模式匹配算法（Brute-Force，BF算法），也叫暴力算法
• 快速模式匹配算法（Knuth-Morris-Pratt，KMP算法）

BF算法

朴素模式匹配算法，其实现过程没有任何技巧，就是简单粗暴地拿一个串同另一个串中的字符一一比对，得到最终结果。

代码实现

public class BruteForce {

    /**
     * @param s 主串
     * @param p 子串
     */
    public static int bruteForce(String s, String p) {
        //匹配初始位置
        int sl = s.length();
        int pl = p.length();
        if (sl < pl) return -1;
        int i = 0, j = 0;
        while (i < sl && j < pl) {
            if (s.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else {//&#x56DE;&#x6EAF;
                i = i - j + 1;
                j = 0;
            }
        }
        if (j >= pl) {//&#x8BF4;&#x660E;&#x5DF2;&#x7ECF;&#x5339;&#x914D;&#x5B8C;&#x6210;
            return i - j;
        } else {//&#x672A;&#x5339;&#x914D;&#x5230;
            return -1;
        }
    }

    public static void main(String[] args) {
        String s = "ZIHUCHUAN";
        String p = "HUA";
        System.out.println(bruteForce(s, p));
    }
}

KMP算法

KMP算法，是一个效率非常高的字符串匹配算法，其核心思想就是主串 不回溯，模式串尽量多地往右移动。

具体实现就是通过一个 next数组实现， next[k]表示的是前 k的字符组成的这个子串 最大公共子串长度。

最大公共子串长度

对于一个字符串来说，它既有前缀，又有后缀，真前（后）缀就是指不包含自身的前（后）缀。

这里的最大公共子串长度，就是指该字符串最长的且相等的真前缀和真后缀。如：

abcd
真前缀: a,ab,abc       前缀：a,ab,abc,abcd
真后缀: bcd,cd,d       后缀: abcd,bcd,cd,d

很明显可以看出，上面的字符串 abcd没有公共前后缀，也就不存在最长公共前后缀了，而对于字符串 abcab，如下：

abcab
真前缀: a,ab,abc,abca   前缀: a,ab,abc,abca,abcab
真后缀: bcab,cab,ab,b   后缀: abcab,bcab,cab,ab,b

其中真前缀 ab和真后缀 ab相等且唯一，即字符串 abcab的最大公共子串长度为 ab，其长度为2。

很明显，从上面的分析可以得出真前缀包含在前缀里面，所以后面 涉及到的前（后）缀都表示真前（后）缀。

构建next数组

next数组的作用是什么？

用来存放最大公共子串的长度，这个长度也就是当主串和子串不匹配的时候，子串需要回退的位置。

最大公共子串的长度作用是什么？

如果 S[i] != P[j]，也就是第一次不匹配，这说明了之前的 j-1（如果存在）个字符都匹配上了，对于这 j-1个字符构成的字符串 P(j-1)，也就是P的子串，我们只需要从P的子串的 最大公共子串处开始下一轮比较即可，主串不需要再回退。

若给定一个主串 BBCABCDABABCDABCDABDE和子串 ABCDABD，在暴力解法中，经过某次匹配后，如下：

此时 S[9]{A} != P[6]{D}，暴力算法是令 i=i-j+1,j=0，通过 回溯的方式重新匹配，但是 i之前的都是已经比较过的，所以如果能保持 i不变， j变为2， 子串右移4位，即 s[9]{A}和 j[2]{C}对齐，如下

（注：上图中的黄色框其实就是暴力算法需要比较的，但实际上却是多余的）

那么我们如何得到这个4位呢？也就是说，我们是怎么知道 j要指向2呢？这就需要用到最大公共子串长度。

在第一张图示中，当 S[9]和 P[6]匹配失衡时：

1. 粉色框中的是匹配的，即 ABCDAB
2. 绿色框和蓝色框匹配，即 AB
3. 蓝色框 AB是粉色框中 ABCDAB的后缀
4. 红色框 AB是粉色框中 ABCDAB的前缀
5. 而蓝色框和红色框都是 AB，说明对于子串中的粉色框 ABCDAB有相等的前后缀，由2可知，绿配蓝，则红色框也和绿色框匹配
6. 所以，将红色框和绿色框对齐，指针 j指向红色框的后一位，从而保持 i不移动，而 j移到位置2，且最大公共子串为 AB，长度为2

由此可知，当 S[i]和 P[j]匹配失衡时，计算出不包括 P[j]的左边子串（ ABCDAB）的最长公共前后缀的长度。假设长度为 k，则 j指针需要重置为 k（如上图中的 j=2）， i不变，继续匹配。

怎么求子串的最大公共长度？

借助 next[]数组， 当子P串在位置 j 失配的时候，需要将 j 指针重置为next[j]，而next[j]就代表了P字符串的子串 P[0~j-1] 的最长公共前后缀，其中对于 next[0]来说，我们一般把他设为 -1（因为 P[0]的左边没有子串，所以 next[0]无法求出）。

如字符串 A,P[0] = A,其左侧没有其他的元素,所以也就不存在前后缀长度了

以子串 ABCDABD为例来构建 next数组：

注：上表中的真前后缀是左边子串的真前后缀

根据上表，我们可得next数组：

由上可知，对于存在最长公共前后缀 k，前缀 P[0~k-1]和后缀 P[j-k~j-1]相等（j>k），则有 next[j]=k，说明 P[j]之前的子串中有长度为 k的前后缀，所以在KMP匹配过程中，当匹配失衡时，只需要将 j移动到 next[j]的位置继续匹配，相当于子串P在原来的位置上右移 next[j]位。

代码实现

因为当 S[i] != P[j]，说明了之前的 j-1个字符都匹配上了，则对 P的子串求出最大公共子串长度即可。又得知next[j] = 第j位字符前面j-1位字符组成的子串的前后缀重合字符数 + 1

首先定义一个 j，从左向右遍历子串P， j的位置表示 P的子串的 后缀的最右字符，再定义一个 k， k的位置用来表示P的子串的 前缀的最右字符

1. 已知 next[j]=k，则 P[0~k-1]=P[j-k~j-1]，前面 k-1位字符和后面的 k-1位字符重合。如当 j=0时， P[0]没有最长前后缀，即 next[0]=-1， j=0,k=-1+1=0，同时 j,k右移进入下一轮循环
2. 我们已经求出 next[j]=k，下一步应该求 next[j+1]，这时分以下两种情况
3. 若 P[j]==P[k]，重复的字符串个数会增加，则 P[0~k-1]+P[k] = P[j-k~j-1]+P[j]，即 P[0~k]=P[j-k~j]，前面 k位字符和后面的 k位字符重合，即多了一位，所以可得出 next[j+1]=k+1，即 next[++j]=++k，如下图
4. 若 P[j]!=P[k]，说明重复的字符串个数不会增加，也就是最大重复子串的长度不能加。这个时候我们要去求 next[j+1]的值，显然这个时候就是要求 j+1位前面的子串，即 P[0~j]的最大重复子串长度。我们假设最长重复子串长度为k1，则

P[j]==P[k]时,最大重复子串长度=k,P[0~k-1]=P[j-k~j-1]
P[j]!=P[k]时,最大重复子串长度=k1,则P[0~k1-1]=P[j+1-k~j]

因为此时最大长度不在增加，所以k1

分析：

1. 给定一个数组如下，假设我们要求 next[16]的值，已知 next[j]=k,next[j+1]=k+1
2. 要求 next[16]的值，即 next[j+1]的值，必然 next[15]的值是已知的，我们假设 next[15]=7，即 j=15,k=7，说明 P[0~k-1]=P[j-k~j-1]的最大公共子串长度为 k=7，则 P[0~6]=P[8~14]
3. 如果 P[7]=P[15]，则 next[16]=next[15]+1=8，就会是下面这种情况，即：

next[j+1]=k+1
next[15+1]=7+1
next[16]=8

– 如果 P[7]!=P[15]，设 next[7]=3，则说明 P[0~6]的最大公共子串长度为3，即 P[0~2]=P[4~6]，由2可知 P[0~6]=P[8~14]，所以以下面蓝色部分是重合的 而 next[7]的值表示的是 P[0~k-1]的最大公共子串长度，所以很明显 P[k]和 p[next[k]]必然不相等，但是 A又和 B相等，所以当 P[7]!=P[15]的时候， 把k的位置重置为 next[k] ，也就是 k=next[k]，这时 k=3，所以此时可以保证 k和j仍有公共前后缀。然后再去判断 p[next[k]]和 P[j]是否相等，若相等则 P[j+1]=k+1,P[16]=3+1 依次类推直到 next[1]=0，说明这时没有公共前后缀。

/**
 * 查找next数组
 */
public static int[] getNext(String p) {
    int len = p.length();
    //构建next表
    int[] next = new int[len];
    int k = -1;//表示后缀的最后以为，
    int j = 0;//表示前缀的最后一位
    //规定next[0]为-1
    next[0] = -1;
    while (j < len - 1) {//&#x5FAA;&#x73AF;p&#x4E32;&#x7684;&#x524D;&#x4E32;
        if (k == -1 || p.charAt(j) == p.charAt(k)) {
            next[++j] = ++k;
        } else {
            k = next[k];
        }
    }
    return next;
}

next数组匹配字符串

1. 当 i=j=0时，若 S[i]==P[j]，字符匹配，i++，j++
2. 若 j=-1，P串需从头匹配，i++，j++
3. S[i]!=P[j]，匹配失衡， j=next[j]

代码实现

public class KMP {

    public static int kmp(String s, String p) {
        //获取next表
        int[] next = getNext(p);
        //匹配初始位置
        int i = 0;
        int j = 0;
        while (i < s.length() && j < p.length()) {
            if (j == -1 || s.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j >= p.length()) {
            return i - j;
        }
        return -1;
    }

    /**
     * 查找next数组
     */
    public static int[] getNext(String p) {
        int len = p.length();
        //构建next表
        int[] next = new int[len];
        int k = -1;//表示后缀的最后以为，
        int j = 0;//表示前缀的最后一位
        //规定next[0]为-1
        next[0] = -1;
        while (j < len - 1) {//循环p串的前串
            if (k == -1 || p.charAt(j) == p.charAt(k)) {
                next[++j] = ++k;
            } else {
                k = next[k];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        int kmp = kmp("BBCABCDABABCDABCDABDE", "ABCDABD");
        System.out.println(kmp);
    }
}

参考

• 字符串及KMP算法
• KMP算法之求next数组代码讲解

Original: https://www.cnblogs.com/javatv/p/15614720.html
Author: Ayue、
Title: BF算法和KMP算法