数组链表算法思路三（KMP算法）

思路

在字符串的比较中，不能双重循环的去做，时间复杂度是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;
    }
}