leetcode459.重复的子字符串

https://leetcode-cn.com/problems/repeated-substring-pattern/

滑动窗口或者kmp算法的next数组

本文使用next数组的性质

class Solution {
   public boolean repeatedSubstringPattern(String s) {
        int[] next = new int[s.length()];
        int j = 0;
        next[0] = 0;
        for(int i = 1;i < next.length;i++){
            while(j > 0 && s.charAt(i) != s.charAt(j)){
                j = next[j - 1];
            }
            if(s.charAt(i) == s.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        int ans = s.length() % (s.length() - next[next.length - 1]);
        if(ans == 0 && next[next.length - 1] > 0) return true;
        else return false;
    }
}
           

思路很简单，就是对字符串s求其next数组，由于next数组的性质，如果字符串是其重复的子字符串多次构成，那么next数组最后一位的值一定是k*len，len是子串的长度。

如果是2个子串构成，则k=1，如果是4个子串构成，则k=3。

因此，s.length()-next[next.length - 1] = 子串的长度， ans = 0则存在，前提是next数组最后一位不为0。

如果为零，那么是不匹配的情况，不符合。