字符串匹配算法（BF、RK、KMP）

爱被打了一巴掌 2023-07-14 05:28 5阅读 0赞

### 文章目录 ###

*   *  BF算法
     *   *   *  时间、空间复杂度
     *  RK算法
     *   *   *  时间、空间复杂度
     *  KMP
     *   *   *  代码实现
             *  时间、空间复杂度

> 字符串匹配问题描述：给定主串str1，模式串str2，在str1找查找str2子串第一次出现的位置，如果存再，则返回str2在str1中第一次的下标，否则返回-1。

## BF算法 ##

全称Brute Force算法，即暴力匹配算法。  
在主串中，检查起始位置分别是0、1、2…n-m且长度为m的n-m+1个子串，看有没有跟模式串匹配的。

/** * @param str1 主串 * @param str2 模式串 * @return 模式串在主串中第一次出现的下标或者-1 */
    public static int bruteForce(String str1, String str2) { 
        int length1 = str1.length();
        int length2 = str2.length();
    
        int index1 = 0; //指向当前比较的str1的下标
        int index2 = 0; //指向当前比较的str2的下标
        int temp = 0; 
    
        while(length1 - index1 >= length2) { 
            temp = index1;
            while(index2 < length2 && str1.charAt(index1) == str2.charAt(index2)) { 
                index1++;
                index2++;
            }
            
            if(index2 == length2) return temp;
            
            index1 = temp + 1;
            index2 = 0;
        }
    
        return -1;
    }

#### 时间、空间复杂度 ####

*  如果模式串长度为m，主串长度为n，那在主串中，就会有n-m+1个长度为m的子串，我们只需要暴力地对比这n-m+1个子串与模式串，因此总共进行（n-m+1）\* m次比较，**时间复杂度为O(n\*m)**。
 *  **空间复杂度为O(1)**

## RK算法 ##

全称Rabin-Karp算法，是该算法发明人Rabin和Karp的名字来命名的。该算法引入哈希算法，不必每次都进行主串中的子串和模式串比较，而是先计算子串和模式串的**哈希值**是否相等，若不相等，表示子串和模式串不匹配，若相等，考虑到哈希冲突，则再依次比较两个串的字符是否匹配。  
哈希值的计算方式有很多种，比如将字符对应的ASCII值相加。

#### 时间、空间复杂度 ####

*  如果我们设计的哈希值不存在哈希冲突，计算主串中的n-m+1个子串的哈希值的时间复杂度为O(n)；模式串和子串一次比较的时间复杂度为O(1)，总共需要比较n-m+1次，**时间复杂度为O(n)**。因此，总的时间复杂度为O(n)。但是如果我们设计的哈希值存在哈希冲突，**最坏情况下，每个子串和模式串的哈希值都相等，则退化成BF算法，时间复杂度达到O(n\*m)**。
 *  **需要存储n-m+1个子串的哈希值，空间复杂度为O(n)**

## KMP ##

KMP是Knuth-Morris-Pratt 的缩写，分别是研究出KMP算法的三个人的名字。  
在BF算法中，当遇到不匹配的字符时，模式串往后移动一位，效率很低。KMP算法就是在视图寻找一种规律：当模式串和主串在匹配过程中，遇到不匹配的字符时，找到一种规律，将模式串往后移动很多位，避免不必要的匹配。

举个例子说明KMP算法的步骤，主串str1 = “BBC ABCDAB ABCDABCDABDE”，模式串str2=“ABCDABD”。

（1）从主串和模式串的第一个字符处开始匹配，不符合则模式串向后移动一位  
![在这里插入图片描述][20200315084535583.png]  
![在这里插入图片描述][20200315084702276.png]  
（2）遇到不匹配的字符  
![在这里插入图片描述][20200315084821437.png]  
当遇到不匹配的字符时，我们已经知道前面已经匹配的字符串子串是“ABCDAB”，KMP的算法的思想是利用这个已知匹配过的子字符串信息，计算出模式串往后移动的位数。这里先了解下前缀子串和后缀子串的概念：  
ABCDAB的前缀子串有：A、 AB、 ABC、 ABCD、 ABCDA  
ABCDAB的后缀子串有：B、 AB、 DAB、 CDAB、 BCDAB

此外，将不匹配的字符称为“坏字符”，已经匹配过的字符串称为“好前缀”：  
![在这里插入图片描述][20200315090913375.png]  
我们只需要从主串的**好前缀的后缀子串**和模式串的**好前缀的前缀子串**中找到最长能匹配的字符串的长度即可，上例中，这个最长能匹配的字符串就是“AB”，长度为2。模式串往后移动的位数就是**好前缀串的长度-2**，也就是让主串的**好前缀的后缀子串**和模式串的**好前缀的前缀子串**最长能匹配的字符串重合：  
![在这里插入图片描述][20200315091344688.png]  
因此KMP的核心思想就是：遇到坏字符时，如果此时模式串中已经匹配上的字符串长度为k（即好前缀长度），主串的**好前缀的后缀子串**和模式串的**好前缀的前缀子串**中最长能匹配的字符串的长度为v，则模式往后移动的位数就是k-v。**那么如何得到v呢？**  
在KMP算法中，定义了一个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数组就是`[0,0,0,0,1,2,0]`，数组下标值加1代表字符串长度，**值代表该字符串前缀和后缀共有元素长度，也就是我们要计算的v值**。当好前缀是“ABCDAB”的时候，v=2，模式串后移4位；当好前缀是“AB”的时候，v=0，模式串后移2位。

（3）接着最开始的那个例子进行，此时好前缀是“AB”，模式串后移2位  
![在这里插入图片描述][20200315093607880.png]  
（4）空格和A不匹配，没有好前缀，模式串往后移动一位  
![在这里插入图片描述][20200315093804289.png]  
（5）好前缀是“ABCDAB”，k=6，v=2，模式串往后移动4位  
![在这里插入图片描述][20200315094023718.png]  
（6）模式串全部匹配，结束。

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

next数组的计算，可以将子串的前缀和后缀都计算出来，然后找最长匹配串长度，就和上面以”ABCDABD”为例讲解next数组列出的步骤一样，这种做法效率低。好的做法是类似动态规划，当计算next\[i\]的时候，前面的next\[0\]，next\[1\]，……，next\[i-1\]应该已经计算出来了，已经计算出来的next值，我们可以快速推导出next\[i\]的值。

public class KMPDemo { 
        public static void main(String[] args) { 
            System.out.println(kmp("BBC ABCDAB ABCDABCDABDE", "ABCDABD"));
        }
    
        /** * @param str1 主串 * @param str2 模式串 * @return 下标 */
        public static int kmp(String str1, String str2) { 
            int length1 = str1.length();
            int length2 = str2.length();
            if(0 == length1 || 0 == length2) return -1;
    
            int[] next = getNext(str2);
    
            for(int i = 0, j = 0; i < length1; i++) { 
                while(j > 0 && str1.charAt(i) != str2.charAt(j)) { 
                    j = next[j - 1];
                }
    
                if(str1.charAt(i) == str2.charAt(j)) { 
                    j++;
                }
    
                // 模式串都能匹配上，返回下标
                if(j == length2) { 
                    return i - j + 1;
                }
            }
    
            return -1;
        }
        
        public static int[] getNext(String str) { 
            int length = str.length();
            int[] next = new int[length];
            // 字符串长度是1的时候，前缀和后缀最长匹配串长度为0
            next[0] = 0;
            
            for(int i = 1, j = 0; i < length; i++) { 
                while (j > 0 && str.charAt(i) != str.charAt(j)) { 
                    j = next[j - 1];
                }
                
                if(str.charAt(i) == str.charAt(j)) { 
                    j++;
                }
                
                next[i] = j;
            }
            
            return next;
        }
    }

#### 时间、空间复杂度 ####

*  next数组的大小和模式串相同，因此**空间复杂度为O(m)**，m为模式串的长度
 *  时间复杂度分为两部分，计算next数组的时间和借助next数组匹配的时间。  
    计算next数组时，外层for循环进行了m-1次，内部while循环总执行次数不可能超过m，因此这部分时间复杂度为O(m)；第二部分时间复杂度计算类似，外层for循环执行n次（n为主串的长度），内部while循环总执行次数不可能超过n，因此这部分时间复杂度为O(n)。  
    总的**时间复杂度为O(m+n)**

[20200315084535583.png]: /images/20230529/cdaddb57af874affa7d5ca31c2139c7c.png
[20200315084702276.png]: /images/20230529/2e3c7c9e16e4482f9347d22eb6119ae2.png
[20200315084821437.png]: /images/20230529/aafde2d7ce6a46749aadb330b4129f44.png
[20200315090913375.png]: /images/20230529/ac31d53778bf426aadc946ab54f0b9b8.png
[20200315091344688.png]: /images/20230529/95b0d6ee6cb34459a3ce99decf649cbf.png
[20200315093607880.png]: /images/20230529/bed59266578e40beb3a24391fb495c3a.png
[20200315093804289.png]: /images/20230529/011ac089b89c4f42a4b770dfa74cc699.png
[20200315094023718.png]: /images/20230529/5856407d5437483eb8815a0f375c139b.png