重复的子字符串

碰到一道算法题，可以按照以下思考流程举行，克制没有思绪。
一.暴力遍历罗列 -> 2.模拟利用 ->3.常用的算法本领或题型，比如双指针，滑动窗口，动态规划，回溯算法之类
通常末了的解法都是在暴力遍历或罗列或模拟利用办理的过程中，发现题目的内涵性子，从而找到更好的方法。
但是除了数学建模这类的题目，要使用数学知识，其他的本质还是穷举出全部的效果，只不外动态规划发现了最优子结构，回溯举行了剪枝，不必列出全部的效果，不重复，不遗漏。
1.暴力罗列
罗列子字串长度分别为1,2,3,......, str.size() / 2，按子串长度区间去匹配，判定是否能构成字串str。
比方：abcabcabc，罗列子串长度为2时，每个i, str == str[i - 2],假如不相称，阐明不能构成该字串。
参考代码：

2. class Solution {
3. public:
4.     bool repeatedSubstringPattern(string s) {
5.         for (int i = 1; i * 2 <= s.size(); ++i) {//遍历所有可能的子串长度
6.             if (s.size() % i == 0) {//判断是否能组成该字串
7.                 bool matchFlag = true;
8.                 for (int j = i; j < s.size(); ++j) {
9.                     if (s[j] != s[j - i]) {
10.                         matchFlag = false;
11.                         break;
12.                     }
13.                 }
14.                 if (matchFlag)
15.                     return true;
16.             }
17.         }
18.         return false;
19.     }
20. };

复制代码

只要把握暴力罗列即可，下面的解法大概想不到，可以死记硬背下来，看成结论使用。
2.根据重复子串构成字串的性子:假设字串为s,那么ss字串去除首字母和尾字母的字串str，假如str中包罗s,那么s是由自身某个子串重复构成的。各人可以自行搜刮证明。
参考代码：使用Kmp算法举行子串匹配

2. class Solution {
3. public:
4.     bool repeatedSubstringPattern(string s) {
5.         string str = s + s;
6.         //构建next数组
7.         vector<int> next(s.size(), 0);
8.         for(int i = 1, j = 0; i < s.size(); ++i){
9.             while(j > 0 && s[j] != s[i]){
10.                 j = next[j - 1];
11.             }
12.             if(s[j] == s[i]){
13.                 ++j;
14.             }
15.             next[i] = j;
16.         }
17.         //匹配子串
18.         for(int i = 1, j = 0; i < str.size() - 1; ++i){
19.             while(j > 0 && str[i] != s[j]){
20.                 j = next[j - 1];
21.             }
22.             if(str[i] == s[j]){
23.                 j++;
24.             }
25.             if(j == s.size())
26.                 return true;
27.         }
28.         return false;
29.     }
30. };

复制代码