字符串BF算法和KMP算法

冷不防 2023-10-03 14:06 16阅读 0赞

### 什么是串 ###

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

一般地，由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`，则：
    
    ![4df11bc5af42e43453ba58fb075facb8.png][]

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

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

### BF算法 ###

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

![image-20210811000042488][]

#### 代码实现 ####

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 {
        //回溯
                    i = i - j + 1;
                    j = 0;
                }
            }
            if (j >= pl) {
        //说明已经匹配完成
                return i - j;
            } else {
        //未匹配到
                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`，在暴力解法中，经过某次匹配后，如下：

![image-20210811234948723][]

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

![image-20210812170703163][]

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

那么我们如何得到这个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]`无法求出）。

![image-20210813115549214][]

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

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

![image-20210812151136382][]

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

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

![image-20210812173258814][]

由上可知，对于存在最长公共前后缀`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]`位。

![image-20210813094142864][]

**代码实现**

因为当`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]`，这时分以下两种情况
    
     *  若`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`，如下图
    
    ![image-20210813201437948][]
    
     *  若`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 <= k，也就是说现在的最大重复子串可能存在于`P[0~k-1]`，也就是`next[k]`的值表示前k个元素的最大重复子串，如下分析

**分析**：

1.  给定一个数组如下，假设我们要求`next[16]`的值，已知`next[j]=k,next[j+1]=k+1`
    
    ![image-20210813232331610][]
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]`
    
    ![image-20210814132612089][]
    
     *  如果`P[7]=P[15]`，则`next[16]=next[15]+1=8`，就会是下面这种情况，即：
        
            next[j+1]=k+1
            next[15+1]=7+1
            next[16]=8
        
        ![image-20210814132851654][]
     *  如果`P[7]!=P[15]`，设`next[7]=3`，则说明`P[0~6]`的最大公共子串长度为3，即`P[0~2]=P[4~6]`，由2可知`P[0~6]=P[8~14]`，所以以下面蓝色部分是重合的
        
        ![image-20210814153508423][]
        
        而`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) {
              //循环p串的前串
                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]
 *  [KMP算法之求next数组代码讲解][KMP_next]

[4df11bc5af42e43453ba58fb075facb8.png]: https://img-blog.csdnimg.cn/img_convert/4df11bc5af42e43453ba58fb075facb8.png
[image-20210811000042488]: https://img-blog.csdnimg.cn/img_convert/d772a9af2b2d78fc49f2c85a5bc60524.png
[image-20210811234948723]: https://img-blog.csdnimg.cn/img_convert/cccd9d63f525ff57a0b6d02c803c1a10.png
[image-20210812170703163]: https://img-blog.csdnimg.cn/img_convert/6e2e3fb660af6bad0333582250e524d3.png
[image-20210813115549214]: https://img-blog.csdnimg.cn/img_convert/cc2f953628b3a8a3950ea1464d425859.png
[image-20210812151136382]: https://img-blog.csdnimg.cn/img_convert/8a3506cc9610d14e2acd5a3861f2e381.png
[image-20210812173258814]: https://img-blog.csdnimg.cn/img_convert/f7c4f3d59c12b9433ce77835ac64be3b.png
[image-20210813094142864]: https://img-blog.csdnimg.cn/img_convert/f22fc21c4daf5cb7e59918829155e54e.png
[image-20210813201437948]: https://img-blog.csdnimg.cn/img_convert/8df7c15193ed5c8b50c9bff0f9e8bec3.png
[image-20210813232331610]: https://img-blog.csdnimg.cn/img_convert/563b7ba6e886469513cc3242a2d5f158.png
[image-20210814132612089]: https://img-blog.csdnimg.cn/img_convert/5203183d27dcb960444aecdfcad2a682.png
[image-20210814132851654]: https://img-blog.csdnimg.cn/img_convert/19c83357c6d29987501aa0ec1eef1889.png
[image-20210814153508423]: https://img-blog.csdnimg.cn/img_convert/b14fb5711cb748d4ca2101dccf708ecd.png
[KMP]: https://blog.csdn.net/ShannonNansen/article/details/76359423
[KMP_next]: https://www.bilibili.com/video/BV16X4y137qw