作者 | 刘助教&本助教
编辑 | 九章算法
对于一个非空字符串，判断其是否可由一个子字符串重复多次组成。
字符串只包含小写字母且长度不超过10000。
输入 "abab"
输出 True
样例解释
输入可由"ab"重复两次组成
输入 "aba"
输出 False
输入 "abcabcabcabc"
输出 True
样例解释
输入可由"abc"重复四次组成
一个简单的思路是，枚举子字符串的长度lenSub则返回True，如果对于所有lenSub均不满足该条件，则返回False。时间复杂度为O(len*v(len))，其中v(len)为len的因数个数（因为我们只需要对整除len的lenSub进行进一步判断）。
下面再说一种神奇的方法，由kmp算法中的next数组实现。
1.字符串s的下标从0到n-1，n为字符串长度，记s(i)表示s的第i位字符，s(i,j)表示从s的第i位到第j位的子字符串，若i>j，则s(i,j)=””(空串）。
2.next数组的定义为：next(i)=p，表示p为小于i且满足s(0 , p) = s(i-p , i)的最大的p，如果不存在这样的p，则next(i) = -1，显然next(0) = -1。我们可以用O(n)的时间计算出next数组。假设我们已知next(0)，next(1)，……，next(i-1) ，现在要求next(i)，不妨设next(i-1) = j0，则由next数组定义可知s(0 , j0) = s(i-1-j0 , i-1)。
若s(j0+1) = s(i)，则结合s(0 , j0) = s(i-1-j0 , i-1)可知s(0 , j0+1) = s(i - (j0+1) , i)，由此可知，next(i)=j0+1。
若s(j0+1)!=s(i)但s(next(j0)+1)=s(i)，记j1=next(j0)，则s(j1+1)=s(i)，由next数组的定义，s(0 , j1) = s(j0 - j1 , j0) = s(i - 1 - j1 , i - 1)，即s(0，j1) = s(i - 1 - j1 , i - 1)，由假设s(j1+1) = s(i)，则s(0 , j1+1) = s(i - (j1+1) , i)，故next(i) = j1+1。
同前两步的分析，如果我们能找到一个k，使得对于所有小于k的k0，s(j(k0)+1)!=s(i)，但有s(j(k)+1) = s(i)，则由next数组的定义可以得到next(i)=j(k)+1，否则需进一步考虑j(k+1) = next(j(k))，如果我们找不到这样的k，则next(i)=-1。
3.对于字符串s，如果j满足，0
4.利用已算出的next(n-1)，令k=n-1-next(n-1)，由c可知，若k整除n，且k
参考代码给出了利用next数组求解的代码。
这道题的第一种解法比较简单，考察穷举和字符串处理的能力，给出第一种方法并正确分析时间复杂度基本可以达到hire；如果面试者对KMP算法有了解，可以给出第二种next数组的算法可以达到strong hire。
http://www.jiuzhang.com/solutions/repeated-substring-pattern/
http://www.lintcode.com/zh-cn/problem/strstr/
回复“简历”，查看简历撰写指南，获取“简历模板”
回复“冷冻期”，查看北美各大IT企业冷冻期信息和注意事项
回复“Career”, 查看Caireer Fair 攻略 check list
回复“薪资”，查看北美各大IT企业New Grades Engineer 薪资水平；
回复“项目”，查看7-14天可以搞定的小项目推荐
回复“评分”，查看系统设计评分指南
回复“behavior”，查看behavior interview指南
回复“晋升”，查看Engineer晋升机制
《系统设计班》
《Big Data 项目实战班》
正在报名中！
报名登陆官网 www.jiuzhang.com
或点击文末“阅读原文”
九章算法版权所有，谢绝转载
