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。

如果為零，那麼是不比對的情況，不符合。