题目描述

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过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;
    }
};

参考链接

https://leetcode-cn.com/problems/repeated-substring-pattern/solution/cppjie-fa-zhou-qi-chuan-by-brianyi/