Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000. Example 1:
Input: “abab” Output: True Explanation: It’s the substring “ab” twice.
Example 2:
Input: “aba” Output: False
Example 3:
Input: “abcabcabcabc” Output: True Explanation: It’s the substring “abc” four times. (And the substring “abcabc” twice.)
方法一：将目标串复制一下拼在一起，知道串头串尾的字母与模式串是相同的，去掉串头串尾后若还能找到原字符串，说明其可由子串复制。
class Solution { public: bool repeatedSubstringPattern(string s) { if(s.empty()) return false; int len=s.size(); string s1=s+s; string s2(s1.begin()+1,s1.end()-1); return s2.find(s)!=-1; } };方法二：暴力匹配 分段后看能否复原原串
class Solution { public: bool repeatedSubstringPattern(string s) { if(s.size()<2) return false; int len=s.size(); for(int i=len/2;i>=1;i--)//子串最大长度为一半 { if(len%i==0) { int cnt=len/i; string t=""; for(int j=0;j<cnt;++j) { t +=s.substr(0,i);//将这些子串拼在一起 } if(s==t) return true; } } return false; } };