[459]重复的子字符串

//给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。 
//
// 示例 1: 
//
// 
//输入: "abab"
//
//输出: True
//
//解释: 可由子字符串 "ab" 重复两次构成。
// 
//
// 示例 2: 
//
// 
//输入: "aba"
//
//输出: False
// 
//
// 示例 3: 
//
// 
//输入: "abcabcabcabc"
//
//输出: True
//
//解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
// 
// Related Topics 字符串 
// 👍 499 👎 0

/*
* 459 重复的子字符串
* 2021-06-11 19:57:37
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        // next数组
        vector<int> next(n);
        next[0] = -1;
        int j = -1;
        // 注意i从1开始
        for(int i = 1;i < n;i++){
          while(j > -1 && s[i] != s[j+1]) j = next[j];
          if(s[i] == s[j+1]) j++;
          next[i] = j;
        }
        // next[n-1] - 1 减1是因为从-1开始计算
        return next[n-1] != -1 && n % (n - next[n-1] - 1) == 0;
    }
};
//leetcode submit region end(Prohibit modification and deletion)