leetcode 459. 重复的子字符串

一、题目

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。

示例 2:
输入: "aba"
输出: False

二、解法

暴力：
若为true，则该子串必定是前缀，且满足\(s[j]==s[j-i]\)（i为子串长度）。小优化：由于子串重复次数至少为2，则子串长度不能超过字符串长度一半。

func repeatedSubstringPattern(s string) bool {
    len:=len(s)
    for i:=1;i<=len/2;i++{
        if len%i==0{
            match:=true
            for j:=i;j

func repeatedSubstringPattern(s string) bool {
    next:=buildNext(s)
    len:=len(s)
    return next[len-1]!=0&&len%(len-next[len-1])==0
}

func buildNext(s string) []int{
    len:=len(s)
    next:=make([]int,len)
    for i,now:=1,0;i