java数据结构和算法——暴力匹配算法

一、字符串匹配问题示例需求

• 有一个字符串 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。

三、暴力匹配算法——实现字符串匹配问题代码示例

1、代码

package com.rf.springboot01.Algorithm.kmp;

/**
 * @description:  暴力匹配算法  实现字符串匹配问题
 * @author: xiaozhi
 * @create: 2020-11-02 22:31
 */
public class ViolenceMatch {
    public static void main(String[] args) {
        String str1 = "天气很好啊 天气很好 今天天气很好啊非常好很好";
        String str2 = "天气很好啊非常好";
        String str3 = "天气很好啊~";
        int index = violenceMatch(str1, str2);
        int index2 = violenceMatch(str1, str3);
        System.out.println("匹配数组下标index=" + index);
        System.out.println("匹配数组下标index2=" + index2);
    }

    public static int violenceMatch(String str1,String str2){
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();

        int chars1Len=chars1.length;
        int chars2Len=chars2.length;

        int i = 0; // i索引指向chars1
        int j = 0; // j索引指向chars2
        while(i