KMP算法实现

往往最牛逼的算法只需要最简单的步骤！

https://leetcode-cn.com/leetbook/read/array-and-string/cpoo6/

https://www.bilibili.com/video/BV1jb411V78H?from=search&seid=2530545103228151131

建议先看文字解析，看不懂再看视频解析。理解了就很简单。

java代码实现 写错了 求next[] 出现问题。求法出错了。明天改正！！！！！！！！！！！！！

package com.ppl.leet01.test;

/**
 * KMP 算法的实现
 * 匹配字符串
 *
 * @author ppliang
 * @date 2021/1/13 17:23
 */
public class KMP {
          
   
    public static boolean hasSubString(String originStr, String subString) {
          
   
        if ((null != originStr && null != subString) && (originStr.length() < subString.length())) {
          
   
            return false;
        }
        char[] originStrChars = originStr.toCharArray();
        char[] subStringChars = subString.toCharArray();
        return matchString(originStrChars, subStringChars);
    }

    /**
     * KMP中的核心算法，获得记录跳转状态的next数组
     *
     * @param c
     * @return
     */
    public static int[] matchTable(char[] c) {
          
   
        int length = c.length;
        int[] a = new int[length];
        int i, j;
        a[0] = -1;
        i = 0;
        for (j = 1; j < length; j++) {
          
   
            i = a[j - 1];
            while (i >= 0 && c[j] != c[i + 1]) {
          
   
                i = a[i];
            }
            if (c[j] == c[i + 1]) {
          
   
                a[j] = i + 1;
            } else {
          
   
                a[j] = -1;
            }
        }
        return a;
    }

    /**
     * 匹配字符串
     *
     * @param originStrChars
     * @param subStringChars
     * @return
     */
    public static boolean matchString(char[] originStrChars, char[] subStringChars) {
          
   
        int[] next = matchTable(subStringChars);
        int i = 0;
        int j = 0;
        while (i <= originStrChars.length - 1 && j <= subStringChars.length - 1) {
          
   
            if (j == -1 || originStrChars[i] == subStringChars[j]) {
          
   

                i++;
                j++;
            } else {
          
   
                if(j<1){
          
   
                    j=next[j];
                }else {
          
   
                    j = next[j-1]+1;
                }
            }
        }
        if (j < subStringChars.length) {
          
   
            return false;
        } else
            return true;
    }

    public static int strStr(String haystack, String needle) {
          
   
        if(needle==null||needle.length()<1){
          
   
            return 0;
        }
        if(haystack==null||haystack.length()<1){
          
   
            return -1;
        }
        int[] next = matchTable(needle.toCharArray());
        char[] originStrChars = haystack.toCharArray();
        char[] subStringChars = needle.toCharArray();
        int index=0;
        int i = 0;
        int j = 0;
        while (i <= originStrChars.length - 1 && j <= subStringChars.length - 1) {
          
   
            if (j == -1 || originStrChars[i] == subStringChars[j]) {
          
   
                if(j==-1){
          
   
                    index=i+1;
                }
                i++;
                j++;
            } else {
          
   
                if(j<1){
          
   
                    j=next[j];
                }else {
          
   
                    j = next[j-1]+1;
                    index=i-j;
                }
            }
        }
        if (j < subStringChars.length) {
          
   
            return -1;
        } else
            return index;
    }
    public static void main(String[] args) {
          
   

        String str1 = "2mississippi";
        String str2 = "issip";
        int[] ints = matchTable(str2.toCharArray());
        for (int i = 0; i <ints.length ; i++) {
          
   
            System.out.print(ints[i]+" ");
        }
        System.out.println();

        boolean b = hasSubString(str1, str2);
        System.out.println("b = " + b);

        int i = strStr(str1, str2);
        System.out.println("i = " + i);
    }
}