1.拿到题目首先想到的便是暴力解法，子字符串的长度从1开始尝试，如果不行就将长度加1。其中可以添加一些剪枝操作，比如子字符串长度一定小于原字符串长度的一半、原字符串长度一定为子字符串长度的整数倍。完整代码如下：

 1. bool repeatedSubstringPattern(char* s) {
 2.     // 获取字符串总长度
 3.     int len = strlen(s);
 4.     // mem代表子串长度，最多到一半长度
 5.     int mem;
 6.     
 7.     // 枚举所有可能的子串长度
 8.     for (mem = 1; mem <= len / 2; mem++){
 9.         // 总长度不能被子串长度整除，不可能重复拼接得到原串，跳过
10.         if (len % mem != 0) continue;
11.  
12.         // 从第二个子串开始逐位对比
13.         for (int i = mem; i < len; i++){
14.             // 当前字符和对应子串内字符不匹配，该长度无效，跳出内层循环
15.             if (s[i] != s[i % mem]) break;
16.             // 全部字符匹配完成，存在重复子串，返回true
17.             if (i == len - 1) return true;
18.         }
19.     }
20.  
21.     // 所有子串长度都尝试完毕，无重复子串
22.     return false;
23. }

该算法时间复杂度为O(n2)，空间复杂度为O(1)。

2.最优的解法是KMP算法，但该算法实在是不容易自己写出来，只能把答案复制过来：

 1. // KMP匹配函数，判断pattern是否在query中出现
 2. bool kmp(char* query, char* pattern) {
 3.     int n = strlen(query);
 4.     int m = strlen(pattern);
 5.     // fail数组：next前缀函数数组
 6.     int fail[m];
 7.     memset(fail, -1, sizeof(fail));
 8.     // 构建pattern的next数组
 9.     for (int i = 1; i < m; ++i) {
10.         int j = fail[i - 1];
11.         // 回退寻找最长相等前后缀
12.         while (j != -1 && pattern[j + 1] != pattern[i]) {
13.             j = fail[j];
14.         }
15.         // 匹配成功，更新fail值
16.         if (pattern[j + 1] == pattern[i]) {
17.             fail[i] = j + 1;
18.         }
19.     }
20.     int match = -1;
21.     // 遍历查询串，跳过首尾字符（拼接后去掉原串首尾）
22.     for (int i = 1; i < n - 1; ++i) {
23.         // 匹配失败，按next数组回退
24.         while (match != -1 && pattern[match + 1] != query[i]) {
25.             match = fail[match];
26.         }
27.         // 当前字符匹配成功，匹配长度+1
28.         if (pattern[match + 1] == query[i]) {
29.             ++match;
30.             // 完整匹配模式串，找到子串
31.             if (match == m - 1) {
32.                 return true;
33.             }
34.         }
35.     }
36.     return false;
37. }
38.  
39. bool repeatedSubstringPattern(char* s) {
40.     int n = strlen(s);
41.     // 拼接 s+s
42.     char k[2 * n + 1];
43.     k[0] = 0;
44.     strcat(k, s);
45.     strcat(k, s);
46.     // 在拼接串掐头去尾后的区间查找原串s，存在则有重复子串
47.     return kmp(k, s);
48. }

该算法的时间复杂度和空间复杂度均为O(n)，是本题的最优解。