LeetCode 459. 重复的子字符串

题目链接：LeetCode 459. 重复的子字符串

题意：

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

解题思路：

本题就是kmp算法的经典应用，n - next[n] 是原字符串的最小周期

完整代码如下：

func repeatedSubstringPattern(s string) bool {
    // kmp的经典应用：求字符串的周期
    
    //求next数组
      m:=len(s)
      s=" "+s
     next:=make([]int,m+1)
      for i,j:=2,0;i<=m;i++{
          for j>0 && s[i] !=s[j+1]{
              j=next[j]
          }
          if s[i]==s[j+1]{
              j++
          }
          next[i] = j
      }
      t:=m-next[m]   //周期
      return t<m && m%t==0
}