目录
LeetCode459.找到重复的子字符串
链接： 459. 重复的子字符串 - 力扣（LeetCode）
方法一：暴力解法
1. 思路
暴力的解法， 就是一个for循环获取 子串的终止位置， 然后判断子串是否能重复构成字符串，又嵌套一个for循环，所以是O(n^2)的时间复杂度。
有的同学可以想，怎么一个for循环就可以获取子串吗？ 至少得一个for获取子串起始位置，一个for获取子串结束位置吧。
其实我们只需要判断，以第一个字母为开始的子串就可以，所以一个for循环获取子串的终止位置就行了。 而且遍历的时候 都不用遍历结束，只需要遍历到中间位置，因为子串结束位置大于中间位置的话，一定不能重复组成字符串。
2. 代码实现
# 暴力解法
# time：O(N^2); space:O(1)
class Solution(object):
def repeatedSubstringPattern(self, s):
"""
:type s: str
:rtype: bool
"""
# 只要判断到字符串的中间位置就可以，
# 因为如果子串长度大于1/2字符串的长度，就不可能由这个重复的子串构成了
for i in range(len(s)//2):
# 截取子串字符串
Str = s[:i+1]
# 前提条件是主串长度可以被子串长度整除
if len(s)%len(Str) == 0:
# 这种Python的写法很棒
# 所有一段段的子字符串都满足条件
if all(s[j:j+len(Str)] == Str for j in range(i+1,len(s),len(Str))):
return True
return False
3. 复杂度分析
时间复杂度：O(N^2)
首先第一个for循环获取子串的结束位置，里面嵌套的for循环是逐个比较主串的元素，整体来说时间复杂度为O(N^2)；
空间复杂度：O(1）
只用到了常数的空间储存子字符串
4. 思考
- Python语言的这种写法，可以记住应用：
if all(s[j:j+len(Str)] == Str for j in range(i+1,len(s),len(Str))):
return True
- 本题只需要遍历子串的结束位置以及只用遍历到字符串中间，这个是需要好好思考一下才能得到的结论，所以写代码之前要好好想想怎么尽可能通过思维上的结论去降低代码实现的复杂度。
方法二：移动匹配
1. 思路
当一个字符串s：abcabc，内部又重复的子串组成，那么这个字符串的结构一定是这样的：
也就是又前后又相同的子串组成。那么既然前面有相同的子串，后面有相同的子串，用 s + s，这样组成的字符串中，后面的子串做前串，前后的子串做后串，就一定还能组成一个s，如图：
所以判断字符串s是否有重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是又重复子串组成。当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。为什么呢？可以画个图片理解一下：
组成新字符串之后，搜索这个字符串里是否出现s，LeetCode28实际上就实现了这个功能。
不过这种解法还有一个问题，就是 我们最终还是要判断 一个字符串（s + s）是否出现过 s 的过程，大家可能直接用contains，find 之类的库函数。 却忽略了实现这些函数的时间复杂度（暴力解法是m * n，一般库函数实现为 O(m + n)）；做过 **28.实现strStr (opens new window)**题目，其实就知道，实现一个 高效的算法来判断 一个字符串中是否出现另一个字符串是很复杂的，这里就涉及到了KMP算法。
2. 代码实现
# 方法二：移动匹配
# time:O(N);space:O(N)
class Solution(object):
def repeatedSubstringPattern(self, s):
"""
:type s: str
:rtype: bool
"""
newStr = s+s
# 去除首尾元素
newStr = newStr[1:len(s)*2-1]
return s in newStr
3. 复杂度分析
时间复杂度：O(N)
字符串长度为N，两个字符串s相加的时间复杂度为O(N)，字符串的切片操作时间复杂度也为O(N），最后一步，查找一个字符串是否在另一个字符串中出现，这个暴力解法的时间复杂度是O(N^2),库函数实现中的时间复杂度一般为O(m+n)，在这里等于O( 2N-2 + N ) = O(N)，所以全部加起来的复杂度仍为O(N）；
空间复杂度：O(N）
储存新的newStr，长度为2n-2，然后实现查找一个字符串是否在另一个字符串中出现的库函数，如果用KMP算法的话，储存next数组也需要O(N）的空间，所以加起来空间复杂度为O(N）。
4. 思考
- 这种思路其实是很巧妙的，如果是遇到新题目很难想到，比起暴力解法，这种方式用空间换了时间；
- 总结Python语言中判断一个字符串是否包含另一个字符串以及有多少个子字符串
>>> a = 'love you'
>>> b = 'you'
>>> c = 'no'
# in 存在则输出True，不存在则输出false
>>> print( b in a)
True
>>> print (c in a)
False
# find() 从左向右查找子串，存在则输出子串首字符的索引值，不存在输出-1
>>> print(a.find(b))
5
>>> print(a.find(c))
-1
# rfind() 从右向左查找子串，存在则输出子串首字符的索引值，不存在输出-1
>>> print(a.rfind(b))
5
>>> print(a.rfind(c))
-1
# index() 从左向右查找子串，存在则输出子串首字符的索引值，不存在则报错
# 适用于确定子串存在于母串中
>>> print(a.index(b))
5
>>> print(a.index(c))
Traceback (most recent call last):
File "<pyshell#18>", line 1, in <module>
print(a.index(c))
ValueError: substring not found
# rindex() 从右向左查找子串，存在则输出子串首字符的索引值，不存在则报错
# 适用于确定子串存在于母串中
>>> print(a.rindex(b))
5
>>> print(a.rindex(c))
Traceback (most recent call last):
File "<pyshell#21>", line 1, in <module>
print(a.rindex(c))
ValueError: substring not found
# count()计数母字符串中有多少个子串
# 不存在则输出0
>>> print(a.count(b))
1
>>> print(a.count(c))
0
>>>
3. Python中的字符串拼接，“+=” 和 ”.join()” 有什么区别？
Python中字符串是不可变对象，修改字符串就得将原字符串中的值复制，开辟一块新的内存，加上修改的内容后写入到新内存中，以达到“修改”字符串的效果。在使用“+”拼接字符串时，正是使用了重复性的复制、申请新内存、写入值到新内存的工作一遍遍的将字符串的值修改。 而使用join()方法拼接字符串时，会先计算总共需要申请多少内存，然后一次性申请所需内存并将字符串复制过去。这样便省去了重复性的内存申请和写入，节省了时间消耗。
方法三：KMP算法
1. 思路：
在一个串中查找是否出现过另一个串，这是KMP的看家本领。那么寻找重复子串怎么也涉及到KMP算法了呢？
KMP算法中next数组为什么遇到字符不匹配的时候可以找到上一个匹配过的位置继续匹配，靠的是有计算好的前缀表。 前缀表里，统计了各个位置为终点字符串的最长相同前后缀的长度。
那么 最长相同前后缀和重复子串的关系又有什么关系呢。
先给出结论：如果是由重复子串构成的主串，那么它的最小重复单元就是 这个主串的最长相等前后缀不包含的那个子串。
这里那字符串s：abababab 来举例，ab就是最小重复单位，如图所示：
如何证明？
步骤一：因为 这是相等的前缀和后缀，t[0] 与 k[0]相同， t[1] 与 k[1]相同，所以 s[0] 一定和 s[2]相同，s[1] 一定和 s[3]相同，即：，s[0]s[1]与s[2]s[3]相同 。
步骤二： 因为在同一个字符串位置，所以 t[2] 与 k[0]相同，t[3] 与 k[1]相同。
步骤三： 因为 这是相等的前缀和后缀，t[2] 与 k[2]相同 ，t[3]与k[3] 相同，所以，s[2]一定和s[4]相同，s[3]一定和s[5]相同，即：s[2]s[3] 与 s[4]s[5]相同。
步骤四：循环往复。
所以字符串s，s[0]s[1]与s[2]s[3]相同， s[2]s[3] 与 s[4]s[5]相同，s[4]s[5] 与 s[6]s[7] 相同。
正是因为 最长相等前后缀的规则，当一个字符串由重复子串组成的，最长相等前后缀不包含的子串就是最小重复子串。
实际上这个推理过程就是重复的使用两点：
- 前缀=后缀
- 错位的前缀和后缀对应主串中同一个位置的元素相等。
结论二： 假设数组长度为len, 最长相等前后缀的长度为：next[len - 1] ；如果len % (len - (next[len - 1] ) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以整除数组的长度，说明有该字符串有重复的子字符串。
数学推导
假设字符串s使用多个重复子串构成（这个子串是最小重复单位），重复出现的子字符串是x，所以s是由n * x组成。
因为字符串s的最长相同前后缀的的长度一定是不包含s本身，所以 最长相同前后缀长度必然是m * x，而且 n - m = 1，（这里如果不懂，看上面的推理）
所以如果 nx % (n - m)x = 0，就可以判定有重复出现的子字符串。
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
强烈建议大家把next数组打印出来，看看next数组里的规律，有助于理解KMP算法
Example：
字符串 a s d f a s d f a s d f
next： 0 0 0 0 1 2 3 4 5 6 7 8
next[len - 1] = 8，8就是此时字符串asdfasdfasdf的最长相同前后缀的长度。
(len - (next[len - 1] ) 也就是： 12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 4正好可以整除12(字符串的长度) ，所以说明有重复的子字符串（asdf）
2. 代码实现
# 方法三 KMP算法
# time:O(N);sapce:O(N)
class Solution(object):
def repeatedSubstringPattern(self, s):
"""
:type s: str
:rtype: bool
"""
# time:O(N);sapce:O(N)
def getNext(s):
Next = [0]*len(s)
j = 0
for i in range(1,len(s)):
while j>0 and s[i] != s[j]:
j = Next[j-1]
if s[i] == s[j]:
j += 1
Next[i] = j
return Next
if len(s) == 0 :
return False
Next = getNext(s)
if Next[-1] == 0 or Next[-1] == len(s):
return False
prefix_len = len(s)-Next[-1]
if len(s)%prefix_len == 0:
return True
return False
3. 复杂度分析
时间复杂度：O(N)
getNext函数中，时间复杂度就为O(N)，后面的时间复杂度也为O(N），总体时间复杂度为O(n)
空间复杂度：O(N）
Next函数的储存，长度就为O(N），然后还有常数个变量，因此整体的空间复杂度为O(N)
4. 思考
- 本题算是KMP算法的一个应用，做起来有一些技巧性在里面，如果没有经验的话很难想到。
Reference：
- (45条消息) Python 字符串拼接 ‘+=‘ 和 ‘join()‘ 谁的速度更快？_程序猿过家家的博客-CSDN博客_python 字符串拼接速度
- (45条消息) Python判断一个字符串是否包含另一个子字符串和有多少个子字符串（全网最全六种方法）_python字符串包含另一个字符串-其它代码类资源-CSDN文库
- 代码随想录 (programmercarl.com)
本题学习时间：180分钟。
字符串总结
双指针总结
两个总结的学习时间：30分钟。