暴力匹配算法实现字符串匹配实战

悠悠 2021-07-24 15:52 393阅读 0赞

# 一 问题引出 #

字符串匹配问题：有一个字符串 str1= "东西南 东北西东 东东西西北南东西东北西南"，和一个字符串 str2="东西西北"，现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1。

# 二 暴力匹配算法 #

如果用暴力匹配的思路，并假设现在str1匹配到 i 位置，子串str2匹配到 j 位置，则有:

1 如果当前字符匹配成功（即str1\[i\] == str2\[j\]），则i++，j++，继续匹配下一个字符。

2 如果不匹配（即str1\[i\]! = str2\[j\]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

3 用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间。不是一个好算法。

# 三 实战 #

1 要求

用暴力匹配算法解决开篇提出的字符串匹配问题。

2 代码

/**
    * @className: ViolenceMatch
    * @description: 字符串匹配暴力破解问题
    * @date: 2021/3/29
    * @author: cakin
    */
    public class ViolenceMatch {
        /**
         * 功能描述：字符串匹配暴力破解问题测试
         *
         * @param args 命令行
         * @author cakin
         * @date 2021/3/29
         */
        public static void main(String[] args) {
            // 测试暴力匹配算法
            String str1 = "东西南 东北西东 东东西西北南东西东北西南";
            String str2 = "东西西北";
            int index = violenceMatch(str1, str2);
            System.out.println("index=" + index);
        }
    
        /**
         * 功能描述：暴力破解算法，在长字符串中匹配短字符串
         *
         * @param str1 长字符串
         * @param str2 短字符串
         * @return 第一次匹配的索引
         * @author cakin
         * @date 2021/3/29
         */
        public static int violenceMatch(String str1, String str2) {
            char[] s1 = str1.toCharArray();
            char[] s2 = str2.toCharArray();
            int s1Len = s1.length;
            int s2Len = s2.length;
            int i = 0; // i索引指向s1
            int j = 0; // j索引指向s2
            // 保证匹配时，不越界
            while (i < s1Len && j < s2Len) {
                if (s1[i] == s2[j]) { // 匹配成功
                    i++;
                    j++;
                } else { // 匹配失败
                    // 指针 i 的位置回退 (j-1)
                    i = i - (j - 1);
                    // 指针 j 的位置回退到 0
                    j = 0;
                }
            }
    
            // 判断是否匹配成功
            if (j == s2Len) {
                // 因为 i 指针 移动了 j 次，所以匹配到的字符串的起始索引是 i - j
                return i - j;
            } else {
                return -1;
            }
        }
    }

3 测试

index=10