代码随想录-KMP算法

 LeetCode28:

 . - 力扣（LeetCode）

public class KMP {
    public static void main(String[] args) {
        KMP kmp=new KMP();
        kmp.strStr("aabaabaaf","aabaaf");
    }
    public int strStr(String haystack, String needle) {
        //获取next数组
        int[] next=getNext(needle);
        //根据next数组，进行匹配
        int i=0;
        for (int j = 0; j < haystack.length()&&j+needle.length()<haystack.length(); j++) {
            while (i>0&&haystack.charAt(j)!=needle.charAt(i)){
                i=next[i-1];
            }
            if (haystack.charAt(j)==needle.charAt(i)){
                i++;
            }
            if (i==needle.length()){
                return j-i+1;
            }
        }
        return -1;
    }

    private int[] getNext(String needle) {
        int[] next=new int[needle.length()];
        next[0]=0;
        int j=0; //前缀的末尾，也是最长相等前后缀的长度
        int i;//后缀的末尾
        for (i = 1; i <needle.length(); i++) {
            while (j>0&&needle.charAt(i)!=needle.charAt(j)){
                j=next[j-1];
            }
            if (needle.charAt(i)==needle.charAt(j)){
                j++;
                next[i]=j;
            }
        }
        return next;
    }

}

LeetCode459:
. - 力扣（LeetCode）

public class LeetCode459 {
    public boolean repeatedSubstringPattern(String s) {
        //查找子串，就是查找s.length-最长前后缀的长度对应的子串
        int[] next = getNext(s);
        if (next[s.length()-1]!=0&&(s.length()%(s.length()-next[s.length()-1])==0)){
            return true;
        }
        return false;
    }
    private int[] getNext(String model){
        int[] next=new int[model.length()];
        next[0]=0;
        int j=0; //前缀的尾部，也是最长前后缀的长度
        int i;//后缀的尾部
        for (i = 1; i <model.length(); i++) {
            while (j>0&&model.charAt(j)!=model.charAt(i)){
                j=next[j-1];
            }
            if (model.charAt(j)==model.charAt(i)){
                j++;
            }
            next[i]=j;
        }
        return next;
    }
}