LeetCode刷题记录：（4）重复的子字符串

leetcode传送通道

/**
重复字符串的next数组是有规律的
abcabc：-1 0 0 0 1 2
abcabcabc：-1 0 0 0 1 2 3 4 5
abcabcabcabc：-1 0 0 0 1 2 3 4 5 6 7 8
abcabcabcabg：-1 0 0 0 1 2 3 4 5 6 7 8 欸嘿，和上面一样，怎么处理？简单，判断一下末尾字符和子串末尾字符是否一样就可以了
*/
根据next数组，一行 if 判断语句就可以搞定
更加详细一些的next数组说明看这里，也不长

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int next[] = getNext(s);
        int L = s.length(); //s的长度 即 next数组长度L
        int subL = L - (next[L-1]+1); //最小子串长度subL = L - next数组末尾元素 (重复串才会满足)
        if(L>1 && L % subL == 0 && s.charAt(L-1) == s.charAt(subL-1)){
            return true;
        }else{
            return false;
        }
    }

    private int[] getNext(String s){
        int[] next = new int[s.length()];
        next[0] = -1;
        int j = -1, i = 0;
        while(i<s.length()-1){
            if(j==-1 || s.charAt(i)==s.charAt(j)){
                next[++i] = ++j;
            }else{
                j = next[j];
            }
        }
        return next;
    }
}