示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。
示例 2:
输入: “aba”
输出: False
示例 3:
输入: “abcabcabcabc”
输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)
来源:力扣(LeetCode)
链接: link.
class Solution { public: void getNext (int* next, const string& s){ next[0] = 0; int j = 0; for(int i = 1;i < s.size(); i++){ while(j > 0 && s[i] != s[j]) { j = next[j - 1]; } if(s[i] == s[j]) { j++; } next[i] = j; } } bool repeatedSubstringPattern (string s) { if (s.size() == 0) { return false; } int next[s.size()]; getNext(next, s); int len = s.size(); if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) { return true; } return false; } };
1.KMP算法