[LeetCode]Repeated Substring Pattern

暴力的解法就是check每个substring看能不能重构s。优化就是对s的长度分解质因数，然后只check长度为因数的substring，时间复杂度可以优化到O(n * sqrt(n))。但是我们还有一种求最长公共前后缀的方法，如果s其有repeat substring，那么其一定存在最长公共前后缀p(p.length < s.length)使得，s.length % (s.length - p.length) == 0。例如，ababab，最长公共前后缀为abab，其满足条件，事实上s.length - p.length就是repeat substring的长度。对于abababa，其最长公共前后缀为aba，则不满足此条件。KMP求next数组就是求最长公共前后缀的方法，具体可以参考这篇文章。时间复杂度O(n)，代码如下：