串匹配--暴力匹配

串匹配--暴力匹配

思路

假设现在长串匹配到 i 位置，子串匹配到 j 位置，则:

1. 如果当前字符匹配成功（即longStr[i]== shortStr[j]），则i++， j++，继续匹配下一个字符
2. 如果不匹配（即longStr[i]! =shortStr[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i都会回溯到i的后一位，j被置为0，然后再进行逐个匹配
3. 用暴力方法解决的话就会有大量的回溯，浪费大量的时间

需求

找出长串中子串首次出现的位置。

从：“望江楼，望江流，望江楼上望江流，江楼千古，江流千古”

搜：“望江楼上''

返回：8

图解

代码

public class ViolentMatch {
    public static void main(String[] args) {
        String s1 = "望江楼，望江流，望江楼上望江流，江楼千古，江流千古";
        String s2 = "望江楼上";

        int result = violentMatch(s1, s2);
        if (result == -1){
            System.out.println("没有匹配到");
        }else{
	    System.out.println("匹配到首次出现的索引位置是：" + result);
	}
        
    }

    public static int violentMatch(String string1, String string2){

        char[] longStr = string1.toCharArray();
        char[] shortStr = string2.toCharArray();

        int longStrLen = longStr.length;        //长串的大小
        int shortStrLen = shortStr.length;      //短串的大小

        int i = 0;  //长串索引
        int j = 0;  //短串索引


        while (i < longStrLen && j < shortStrLen){
            if (longStr[i] == shortStr[j]){
                i++;
                j++;
            }else {
                //回溯
                i = i - j + 1;
                j = 0;	//每次都将短串的索引初始为0
            }

            if (j == shortStrLen){
                return i - j;
            }

        }

        return -1;
    }
}