从暴力匹配算法到KMP算法之字符串匹配问题-蒲公英云

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

你的名字 2023-07-15 09:23 135阅读 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;
        }
    }
}