KMP算法 LeetCode 459. 重複的子字元串

題目

給定一個非空的字元串，判斷它是否可以由它的一個子串重複多次構成。給定的字元串隻含有小寫英文字母，并且長度不超過10000。

示例 1:

輸入: "abab"

輸出: True

解釋: 可由子字元串 "ab" 重複兩次構成。
示例 2:

輸入: "aba"

輸出: False
示例 3:

輸入: "abcabcabcabc"

輸出: True

解釋: 可由子字元串 "abc" 重複四次構成。 (或者子字元串 "abcabc" 重複兩次構成。)
           

解題思路

KMP算法

代碼

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return kmp(s + s, s);
    }

    public boolean kmp(String query, String pattern) {
        int n = query.length();
        int m = pattern.length();
        int[] next = new int[m];
        Arrays.fill(next, -1);
        for (int i = 1; i < m; ++i) {
            int j = next[i - 1];
            while (j >=0 && pattern.charAt(j + 1) != pattern.charAt(i)) {
                j = next[j];
            }
            if (pattern.charAt(j + 1) == pattern.charAt(i)) {
                next[i] = j + 1;
            }
        }
        int j = -1;
        for (int i = 1; i < n - 1; ++i) {
            while (j >=0 && pattern.charAt(j + 1) != query.charAt(i)) {
                j = next[j];
            }
            if (pattern.charAt(j + 1) == query.charAt(i)) {
                ++j;
                if (j == m - 1) {
                    return true;
                }
            }
        }
        return false;
        
    }
}