LeetcodeT459-KMP-next数组求循环节

本题为KMP的next数组的应用，重点在求循环节上。

next函数与T28的相同

    // 寻找next下标，注意-1的越界
    private int[] findNext(char[] p) {
        int[] next = new int[p.length];
        next[0] = -1;
        for (int i = 1; i < p.length; i++) {
            next[i] = -1;
            int t = next[i - 1];
            while (true) {
                if (p[i] == p[t + 1]) {
                    next[i] = t + 1;
                    break;
                } else {
                    if (t == -1) {
                        break;
                    }
                    t = next[t];
                }
            }

        }
        return next;
    }

最初的想法，开头有几个连续的-1，即为循环节，abab abcabcabc这种数据符合，死在了abacabac这种

    public boolean repeatedSubstringPattern(String s) {

        int[] nexts = findNext(s.toCharArray());
        int all = 0;
        int pre = 0;
        boolean flag = false;

        for (int i = 0; i < nexts.length; i++) {
            if (nexts[i] == -1) {
                all++;
                if (!flag) {
                    pre++;
                }
            } else {
                flag = true;
            }
        }

        if (all == pre && nexts.length % pre == 0 && nexts.length /pre>1) {
            return true;
        } else {
            return false;
        }
    }

然后想到的是求最后一个next的值+1 与 总长度的公约数（必须大于1才叫公约数，等于一是互质），即为循环节。坑在了aaaa（就是公约数为1的情况）这种单个循环的用例，打补丁后能过。

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public boolean repeatedSubstringPattern(String s) {

        int[] nexts = findNext(s.toCharArray());

        // 末尾为-1肯定不循环
        if (nexts[s.length() - 1] == -1) {
            return false;
        }

        //解决aaaa这种用例
        if (nexts[s.length() - 1] + 2 == s.length()) {
            return true;
        }

        return gcd(s.length(), nexts[s.length() - 1] + 1) > 1;
}

最后发现结合了两种想法，总长度减去最后一个next的值+1 即为循环节。

    public boolean repeatedSubstringPattern(String s) {

        int[] nexts = findNext(s.toCharArray());
        if (nexts[s.length() - 1] == -1) {
            return false;
        }
        return s.length() % (s.length() - nexts[s.length() - 1] - 1) == 0;

    }

总结：我太难了。。。很多题有印象，知道大概算法，细节部分总是遗漏。

补充：想了想，若循环节是k，总长度就是l，若符合题意最后一个数的next值必为 l - k - 1。 l - k 与 l 的 最大公约数只会是k（l % (l - k) = k）