题目给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。思路具体代码实现(C++)模型(知识点)
题目 给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。示例 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算法
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)