从暴力匹配算法到KMP算法之字符串匹配问题

你的名字 2023-07-15 09:23 25阅读 0赞

**字符串匹配问题描述**

给定两个字符串，字符串 str = "aabbcabc" ，字符串 regex = "abc" ，判断字符串 str（aabbcabc） 是否 包含 字符串 regex（abc） ,如果包含，则返回regex（abc） 在 str（aabbcabc） 中首次出现的位置，否则返回 -1

（题外话：str.indexOf(regex) 得到结果，不在本文讨论的范畴中）

**一、暴力匹配算法之字符串匹配问题**

暴力匹配算法思路

（1）开始匹配之前， i 指向字符串 str（aabbcabc）中第一个字符的位置，即 i = 0 , j 指向字符串 regex（abc）中第一个字符的位置，即 j = 0

（2）比较字符串 str（aabbcabc）在 i 位置上的字符 与 字符串 regex（abc）在 j 位置上的字符是否相等

（2.1）如果相等，即当前字符匹配成功（strCharArray\[i\] == regexCharArray\[j\]），则 i ++ ， j ++ ，继续比较下一个字符

（2.1）如果不相等，即当前字符匹配失败（strCharArray\[i\] != regexCharArray\[j\]），则 i = i - (j - 1) ，j = 0

i = i - (j - 1) 解释说明：每次匹配失败后，进行下一次字符比较时 i 的位置都是上一次字符匹配开始时 i 的位置 加 1 ，即在判断不包含之前，字符串 str（aabbcabc）中的字符都会被逐一（按下标顺序 0...str.length-1）检索到，并与字符串 regex（abc）中的字符进行比较，图解如下

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 1][]

注意：暴力匹配算法存在大量的回溯，每次只移动一位，如果不匹配，移动到下一位接着判断，浪费了大量的时间，不现实

**代码实现**

package com.zzb.algorithm.kmp;
    
    /**
     * @Auther: Administrator
     * @Date: 2020/3/16 15:18
     * @Description: 暴力匹配算法之字符串匹配问题
     */
    public class ViolenceMatch {
        public static void main(String[] args) {
            // 待匹配字符串
            String str = "aabbcabc";
            // 模式字符串
            String regex = "abc";
    
            int index = violenceMatch(str, regex);
            System.out.println("字符串" + regex + "在字符串" + str + "中首次出现的位置为 " + index);
            /*字符串abc在字符串aabbcabc中首次出现的位置为 5*/
            System.out.println(str.indexOf(regex));
        }
    
        /**
         * 暴力匹配算法
         * @param str 待匹配字符串
         * @param regex 模式字符串
         * @return 模式字符串 在 待匹配字符串 出现，则返回在待匹配字符串中首次出现的位置，否则返回 -1；
         */
        private static int violenceMatch(String str, String regex) {
            char[] strCharArray = str.toCharArray();
            char[] regexCharArray = regex.toCharArray();
            int i = 0; // 待匹配字符串的初始位置，即指针
            int j = 0; // 模式字符串的初始位置，即指针
    
            while(i < strCharArray.length && j < regexCharArray.length) {
                // 如果当前 i 位置的字符 与 当前 j 位置的字符相等，继续比较下一个 i 与 j 位置的字符
                if(strCharArray[i] == regexCharArray[j]) {
                    i ++;
                    j ++;
                }else {
                    // 如果当前 i 位置的字符 与 当前 j 位置的字符不相等，则 i 回溯到 i - (j - 1) 位置
                    // j 重置为 0
                    i = i - (j - 1);
                    j = 0;
                }
            }
    
            // 退出循环
            if(j == regexCharArray.length) { // 找到条件（匹配）
                return (i - j); // 首次出现的位置
            }else { // 没找到（不匹配）
                return -1;
            }
        }
    }

**二、KMP算法之字符串匹配问题**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70]: /images/20230528/a96f49ca390b48008d549c34b1369509.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70 1]: /images/20230528/914ae75454c64f3e9da202aba8a77a45.png