KMP 算法

KMP算法讲解：
链接： https://www.youtube.com/watch?v=GTJr8OvyEVQ

KMP算法就是先将pattern对应的index存进array，然后按照该array进行search。

解题思路：


代码：

public class KMP {
    /**     * Compute temporary array to maintain size of suffix which is same as prefix     * Time/space complexity is O(size of pattern)     */    private int[] computeTemporaryArray(char pattern[]){
        int[] lps = new int[pattern.length];
        int j = 0;
        int i = 1;
        lps[0] = 0;
        while(i <= pattern.length - 1){
            if(pattern[i] == pattern[j]){
                lps[i] = j + 1;
                i++;
                j++;
            }
            else if(j == 0){
                lps[i] = 0;
                i++;
            }
            else{
                j = lps[j - 1];
            }
        }
        return lps;
    }

    /**     * KMP algorithm of pattern matching.     */    public boolean KMP(char[] text, char[] pattern){

        int[] lps = computeTemporaryArray(pattern);
        int i=0;
        int j=0;
        while(i < text.length && j < pattern.length){
            if(text[i] == pattern[j]){
                i++;
                j++;
            }else{
                if(j != 0){
                    j = lps[j-1];
                }else{
                    i++;
                }
            }
        }
        if(j == pattern.length){
            return true;
        }
        return false;
    }

    public static void main(String args[]){

        String str = "abcxabcdabcdabcy";
        String subString = "abcdabcy";
        KMP ss = new KMP();
        boolean result = ss.KMP(str.toCharArray(), subString.toCharArray());
        System.out.print(result);

    }
}