文章目录

• 1. 题目
• 2. 思路
• • (1) KMP
• 3. 代码

1. 题目

2. 思路

(1) KMP

• 对字符串求解KMP算法中的next数组，可以得到字符串的最长相等前后缀的长度。
• 若字符串s是由重复的子字符串s’组成，则s=s’s’…s’s’，显然，字符串的长度减去最长相等前后缀的长度即为重复的子字符串s’的长度。
• 因此，若最长相等前后缀的长度不为0，且字符串的长度减去最长相等前后缀的长度能够被字符串的长度整除，则表示字符串是由重复的子字符串组成。

3. 代码

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        int[] next = new int[n];
        int j = 0;
        for (int i = 1; i < n; 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;
        }
        if (next[n - 1] == 0 || n % (n - next[n - 1]) != 0) {
            return false;
        }
        return true;
    }
}