思路
在字符串的比较中，不能双重循环的去做，时间复杂度是n^2，需要进行简化
例子：（KMP）
有s,m两个字符串，s= abcdabcdx,m=abcdx,请找出m子串在s中起始位置。
按照我们的常规思路我们会将m和s的每一个字符比较（有两个游标i,j，分别指向两个字符串的开头）：
1.如果m的第一个字符与s中的某一个位置的字符相等（比如：第一个），然后继续移动i,和j, i++ ,j++
2.如果m中的某一个字符与s中不相等，就需要将两个指针重新定位
image.png
仔细看上图的几步：当第一步匹配失败后，其实第二步和第三步其实是没有用，一定是无效比较的。所有我们伟大的两位科学家就找出了规律。
规律：
1.当s字符串被比较的部分前后缀相同时，如s前后缀为 abcdabcdx，当然cd也是后面其中一部分的后缀。
2.这个时候，就可以直接跳过中间部分，直接跳到图中 真正有效的第二步那样的情况
3.这样就大大减少了比较的次数
所以这个算法的重点：
1.找到s字符串每一个字符以前的前后缀的长度数组LPS[]
2.在比较的过程中进行跳跃
代码中有些细节还需要以后补充
package com.han.leetcode.kmp;
import java.util.Arrays;
/**
* 首先要找到公共前后缀
* 使用前后指针，如果不相同以后有指针，相同两个一起移动
* 同时左指针来记录长度为len的字串长度
* <p>
* 表示j之前的下一个前后缀的长度，比如连续相等的情况就可以向后退一步来继续比较
* 这是有指针需要继续不动
*
* 通过上面lps数组进行跳跃
* 如果j移动过，表示lps数组有值可以进行跳跃否则只能继续比较开头
*/
public class KMPMatcher {
public static void main(String[] args) {
String haystack = "ABAxAB";
int[] ps = new KMPMatcher().prixSuffix(haystack);
int index = new KMPMatcher().indexof(haystack, "ABH", ps);
System.out.println(Arrays.toString(ps));
System.out.println("位置："+index);
}
private int indexof(String s, String m, int[] ps) {
if(m.length() == 0)
return 0;
int j = 0;
for (int i = 0; i < s.length(); ) {
if (s.charAt(i) == m.charAt(j)) {
j++;
i++;
} else if(j > 0){//如果j移动过，表示lps数组有值可以进行跳跃否则只能继续比较开头
j = ps[j-1];
}else {
i++;
}
if (j == m.length())
return i - m.length();
}
return -1;
}
/**
* 两个指针第一个指针（也可以表示前缀的长度）
* 第二个指针不断向后遍历字符串
* 当遇到无法匹配相等的字符串，就尝试进行低于当前前后缀长度i的长度
*
* @param s
* @return
*/
private int[] prixSuffix(String s) {
int len = 0;
int[] ps = new int[s.length()];
ps[0] = 0;
ps[1] = 0;
int j = 1;
while (j < s.length()) {
if (s.charAt(len) == s.charAt(j)) {
ps[j++] = ++len;
} else if (len > 0) {
//表示j之前的上一个一个前后缀的长度，比如连续相等的情况就可以向后退一步来继续比较
len = ps[len - 1];
} else {
j++;
}
}
return ps;
}
}
