LeetCode Repeated Substring Pattern 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.)

---

本题问一个字符串能否由其子串通过复制多次得到。如果能的话，中间肯定有一个字符和第一个字符相同，所以我们只需要遍历中间字符，找到和第一个字符相等的位置，那么这个位置往前就是重复子串pattern，我们再看这个位置往后是否都是pattern的重复。 其实如果字符串确实由pattern重复而来，则这个pattern的长度应该小于等于总长度的一半，所以我们只需要查找总长度的一半来找和第一个字符相同的字符。 完整代码如下： [cpp] class Solution { public: bool repeatedSubstringPattern(string str) { if (str.size() == 1)return false; for (int i = 1; i <= str.size() / 2; ++i) { if (str[i] == str[0]) { string pattern = str.substr(0, i); int j = i; while (j < str.size()) { string sub = str.substr(j, pattern.size()); if (pattern != sub)break; j += pattern.size(); } if (j == str.size())return true; } } return false; } }; [/cpp] 本代码提交AC，用时56MS。]]>