题目描述
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
解题思路
周期串为s,那么设定t表示周期,值在[1,len(s)-1]的范围,那么剩下的就是依次对每个t值进行遍历看是否真的满足周期为t,数学中周期的表达式是
那么代码中可以这样写s[i%t]==s[i]
代码实现
#include<iostream>
#include<string>
#include<unordered_map>
#include<algorithm>
using namespace std;
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int len = s.size(), i = 0, t = 0;
for (t = 1; t <= len / 2; t++) {
if (len % t)continue; // 有余数，一定不是周期串
for (i = t; i < len && s[i%t] == s[i]; i++) {
}
if (i == len) return true;
}
return false;
}
};
