串匹配--暴力匹配
思路
假设现在长串匹配到 i 位置,子串匹配到 j 位置,则:
- 如果当前字符匹配成功(即longStr[i]== shortStr[j]),则i++, j++,继续匹配下一个字符
- 如果不匹配(即longStr[i]! =shortStr[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i都会回溯到i的后一位,j被置为0,然后再进行逐个匹配
- 用暴力方法解决的话就会有大量的回溯,浪费大量的时间
需求
找出长串中子串首次出现的位置。
从:“望江楼,望江流,望江楼上望江流,江楼千古,江流千古”
搜:“望江楼上''
返回: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;
}
}