給出如下兩字串：
String str1=“lovilovilovloveiloveyou”;
String str2=“ilove”;
要求從 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.
代碼實作：

public class BruteForceDemo {
	public static void main(String[] args) {
		String arr="lovilovilovloveiloveyou";
		String target="ilove";
		
		int index = violenceMatch(arr,target);
		System.out.println(index);
	}
	/**
	 * @param str1 被匹配字串
	 * @param str2 待匹配字串
	 * @return 回傳出現的首字母索引
	 */
	public static int violenceMatch(String str1,String str2) {
		char[] s1=str1.toCharArray();
		char[] s2=str2.toCharArray();
		int i=0;//i索引指向s1
		int j=0;//j索引指向s2
		while(i<s1.length&&j<s2.length) {//保證匹配時下標不越界
			if(s1[i]==s2[j]) {//匹配正確時，i,j指標均往后移動
				i++;
				j++;
			}else {//沒有匹配成功時
				//匹配失敗，i回溯，j置0
				i=i-j+1;
				j=0;
			}
		}
		//判斷是否匹配成功
		if(j==s2.length) {
			return i-j;
		}else {
		return -1;
		}
	}
}

弊端：

用暴力方法解決的話就會有大量的回溯，每次只移動一位，若是不匹配，移動到下一位接著判斷，浪費了大量的時間，

KMP演算法：

1）KMP是一個解決模式串在文本串是否出現過，如果出現過，最早出現的位置的經典演算法，
2）KMP演算法利用之前判斷過資訊，通過一個next陣列，保存模式串中前后最長公共子序列的長度，每次回溯時，通過next陣列找到，前面匹配過的位置，省去了大量的計算時間，

圖解：
1.首先，用str1的第一個字符和str2的第一個字符去比較，不符合，關鍵字向后移動一位

2.重復第一步，還是不符合，繼續后移

3.一直重復，直到str1有一個字符與str2的第一個字符符合為止

4.接著比較字串和搜索詞的下一個字符，還是符合

5.直到遇到str1有一個字符與str2的一個字符不匹配

6.這個時候，想到的是繼續遍歷str1的下一個字符，重復第一步，（這樣是很不明智的，因為此時ilov已經比較過了，沒有必要再做重復的作業，一個基本的事實是，當i與e不匹配時，你其實知道前面四個字符是ilov，KMP演算法的想法是，設法利用這個已知資訊，不要把“搜素位置”移動回已經比較過的位置，繼續把它向后移，這樣就提高了效率，）
暴力匹配的思路便是：i=i-j+1 ,j=0:

如果用KMP思想便是：（直接把i的索引回傳到之前匹配過的位置上）

但是這樣是在“lov”中沒有與“i”重復的情況下，
如果有重復，也會有新的問題：
如下：如果是這樣兩個字串

當e與v不匹配時，按照上面思路，ovoe應該直接開始與oe進行匹配，即：

但是顯然，我們此時錯過了第二個o而導致的匹配結果出錯，即當匹配子串的首字符與后面字符有相同時，不應直接放到已匹配字符的后面，
即應該從第二個o重新匹配：

如此我們得到的結果才算正確，
7.那么如何判斷子串在匹配失敗時應該回溯的位置？
我們可以給出一個公式：
子串向后移動的位數=已匹配的字符數-對應的部分匹配值
那么
什么是部分匹配值：
字串：“bread”
前綴：b,br,bre,brea
后綴：read,ead,ad,d
而部分匹配值就是“前綴”和“后綴”的最長的共有元素的長度，
以ovoe為例
“o"的前綴和后綴都為空，所以最長的共有元素的長度為0
"ov"的前綴為“o“，后綴為”v“，最長的共有元素的長度為0
“ovo"的前綴為”o“，”ov“，后綴為”vo”，“o”,最長的共有元素的長度為1
“ovoe"的前綴為”o“，”ov“，”ovo“，后綴為”voe“，”oe“，”e”,最長的共有元素的長度為0

所以ovoe已匹配的字符為”ovo“，其對應的部分匹配值為1，
已匹配的字符數為3，
子串向后移動的位數便是3-1=2；
所以ovoe才從

到

，

代碼實作：

public class KMP {
	public static void main(String[] args) {
		String arr="lovovoe";
		String target="ovoe";
		int[] next=next(target);
		
		int index = kmpMatch(arr,target,next);
		System.out.println(index);
	}
	//先得到子串的部分匹配表
	//獲取到一個字串（子串）的部分匹配值
	public static int[] next(String target) {
		//創建一個next陣列，保存部分匹配值
		int[] next=new int[target.length()];
		next[0]=0;//如果字串長度為1，部分匹配值一定為0
		for(int i=1,j=0;i<target.length();i++) {
			while(j>0&&target.charAt(i)!=target.charAt(j)) {
				j=next[j-1];
			}
			//部分匹配值加1
			if(target.charAt(i)==target.charAt(j)) {
				j++;
			}
			next[i]=j;
		}
		return next; 
	}
	//kmp搜素
	/**
	 * @param str1 源字串
	 * @param str2 子串
	 * @param next 子串對應的部分匹配表
	 * @return 回傳第一個匹配的位置，沒有回傳-1
	 */
	public static int kmpMatch(String str1,String str2,int[] next) {
		 for(int i=0,j=0;i<str1.length();i++) {
			 //考慮str1.charAt(i)!=str2.charAt(j)的情況
			 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()) {
				 return i-j+1;
			 }
		 }
		 return -1;
	}
}