應(yīng)用場(chǎng)景-字符串匹配問(wèn)題
字符串匹配問(wèn)題：：
有一個(gè)字符串 str1= ""你好的乘客就變成了威威成本即可奧爾加本次選舉二點(diǎn)五啦""，和一個(gè)子串 str2="本次選"
現(xiàn)在要判斷 str1 是否含有 str2, 如果存在篮绿，就返回第一次出現(xiàn)的位置, 如果沒(méi)有孵延，則返回-1
解決思路
暴力匹配算法
如果用暴力匹配的思路，并假設(shè)現(xiàn)在str1匹配到 i 位置亲配，子串str2匹配到 j 位置尘应，則有:
如果當(dāng)前字符匹配成功（即str1[i] == str2[j]），則i++吼虎，j++菩收，繼續(xù)匹配下一個(gè)字符
如果失配（即str1[i]! = str2[j]），令i = i - (j - 1)鲸睛，j = 0。相當(dāng)于每次匹配失敗時(shí)坡贺，i 回溯官辈，j 被置為0。
用暴力方法解決的話就會(huì)有大量的回溯遍坟，每次只移動(dòng)一位拳亿，若是不匹配，移動(dòng)到下一位接著判斷愿伴，浪費(fèi)了大量的時(shí)間肺魁。(不可行!)
暴力匹配算法實(shí)現(xiàn).
public class ViolenceMatch {
public static void main(String[] args) {
String str1 = "暴力破解算法之任意字符串圍毆文憑的么快二u我圍毆的打錯(cuò)了";
String str2 = "圍毆的";
int index = violenceMatch(str1, str2);
System.out.println("index=" + index);
}
// 暴力匹配算法實(shí)現(xiàn)
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) {// 保證匹配時(shí)，不越界
if(s1[i] == s2[j]){
i++;
j++;
} else {
i = i-(j-1);
j=0;
}
}
if(j==s2len){
return i-j;
} else {
return -1;
}
}
}
結(jié)果
KMP算法解決
KMP算法介紹
KMP是一個(gè)解決模式串在文本串是否出現(xiàn)過(guò)隔节，如果出現(xiàn)過(guò)鹅经，最早出現(xiàn)的位置的經(jīng)典算法
Knuth-Morris-Pratt 字符串查找算法，簡(jiǎn)稱為 “KMP算法”怎诫，常用于在一個(gè)文本串S內(nèi)查找一個(gè)模式串P 的出現(xiàn)位置瘾晃，這個(gè)算法由Donald Knuth、Vaughan Pratt幻妓、James H.
Morris三人于1977年聯(lián)合發(fā)表蹦误，故取這3人的姓氏命名此算法.
KMP方法算法就利用之前判斷過(guò)信息，通過(guò)一個(gè)next數(shù)組肉津，保存模式串中前后最長(zhǎng)公共子序列的長(zhǎng)度强胰，每次回溯時(shí)，通過(guò)next數(shù)組找到妹沙，前面匹配過(guò)的位置偶洋，省去了大量的計(jì)算時(shí)間
參考資料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
獲取部分匹配值的代碼實(shí)現(xiàn)如下:
//獲取到一個(gè)字符串(子串) 的部分匹配值表
public static int[] kmpNext(String dest) {
//創(chuàng)建一個(gè)next 數(shù)組保存部分匹配值
int[] next = new int[dest.length()];
next[0] = 0; //如果字符串是長(zhǎng)度為1 部分匹配值就是0
for(int i = 1, j = 0; i < dest.length(); i++) {
//當(dāng)dest.charAt(i) != dest.charAt(j) ，我們需要從next[j-1]獲取新的j
//直到我們發(fā)現(xiàn) 有 dest.charAt(i) == dest.charAt(j)成立才退出
//這時(shí)kmp算法的核心點(diǎn)
while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j-1];
}
//當(dāng)dest.charAt(i) == dest.charAt(j) 滿足時(shí)初烘，部分匹配值就是+1
if(dest.charAt(i) == dest.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
}
核心代碼實(shí)現(xiàn):
public class KMPAlgorithm {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
//String str2 = "BBC";
int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
System.out.println("next=" + Arrays.toString(next));
int index = kmpSearch(str1, str2, next);
System.out.println("index=" + index); // 15了
}
//寫(xiě)出我們的kmp搜索算法
/**
*
* @param str1 源字符串
* @param str2 子串
* @param next 部分匹配表, 是子串對(duì)應(yīng)的部分匹配表
* @return 如果是-1就是沒(méi)有匹配到涡真，否則返回第一個(gè)匹配的位置
*/
public static int kmpSearch(String str1, String str2, int[] next) {
//遍歷
for(int i = 0, j = 0; i < str1.length(); i++) {
//需要處理 str1.charAt(i) 分俯！= str2.charAt(j), 去調(diào)整j的大小
//KMP算法核心點(diǎn), 可以驗(yàn)證...
while( j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = next[j-1];
}
if(str1.charAt(i) == str2.charAt(j)) {
j++;
}
if(j == str2.length()) {//找到了 // j = 3 i
return i - j + 1;
}
}
return -1;
}
//獲取到一個(gè)字符串(子串) 的部分匹配值表
public static int[] kmpNext(String dest) {
//創(chuàng)建一個(gè)next 數(shù)組保存部分匹配值
int[] next = new int[dest.length()];
next[0] = 0; //如果字符串是長(zhǎng)度為1 部分匹配值就是0
for(int i = 1, j = 0; i < dest.length(); i++) {
//當(dāng)dest.charAt(i) != dest.charAt(j) ，我們需要從next[j-1]獲取新的j
//直到我們發(fā)現(xiàn) 有 dest.charAt(i) == dest.charAt(j)成立才退出
//這時(shí)kmp算法的核心點(diǎn)
while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j-1];
}
//當(dāng)dest.charAt(i) == dest.charAt(j) 滿足時(shí)哆料，部分匹配值就是+1
if(dest.charAt(i) == dest.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
}
結(jié)果:
