LeetCode459.重复的子字符串

题目描述

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

示例

提交的代码

十五分钟内没想出来怎么解决，没代码：(

学习到的东西

因为个人没有想出来怎么解决，看的是Carl大神的解法，地址我放在下面：
移动匹配以及KMP解此题
然后我写一下我个人理解的地方吧，记录下个人笔记。

移动匹配

如果整体字符串是由若干子字符串重复组成的话，那么这个字符串的第一个子字符串和最后一个子字符串一定是相等的。

所以这个字符串两倍拼接在一起的时候，一定可以从拼接的字符串中再次找到这个字符串(除了拼接在一起的第一个和第二个字符串)。下图中橙色框代表可以在新拼接的字符串中搜索的范围(要避开0索引和最后一个索引，毕竟是新拼接在一起的)，红色框则代表从拼接中寻找出原字符串的其中一个。

所以代码思想也很简单，避开新拼接的字符串的0索引和最后一个索引去寻找原来的字符串是否存在于当前新的字符串中，我这里用的Java中的contains方法。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String temp=s;
        s += s;
        s = s.substring(1, s.length()-1);
        return s.contains(temp);
    }
}

KMP算法

KMP算法中的next数组索引位的值就代表当前相等的前后缀的长度，而当前题目的特性是字符串是由子字符串重复构成，那么最长的前后缀一定也是由子字符串构成的，所以最长前后缀的差集一定是子字符串，证明如下。其中绿色代表最长前缀，橙色代表最长后缀，下一张图的红色代表差集。


图中的最长前缀和最长后缀简称为p,s数组，原数组为f。
因为最长前后缀是相等的，所以 p[0]=s[0],p[1]=s[1],p[2]=s[2],而s[0]=f[3],s[1]=f[4],s[2]=f[5];p[0]=f[0],p[1]=f[1],p[2]=f[2],
所以可以证得f[0]=f[3],f[1]=f[4],f[2]=f[5]，重复循环下去就可以证得字符串是由子字符串重复构成。
所以KMP算法来解决这道题的关键在于：如果字符串长度为len，next[len-1]为当前字符串最长的前后缀长度，且如果当前字符串真的是由子字符串重复构成，那么len%(len-next[len-1])==0。
代码如下：

class Solution {
    //KMP算法实现查找重复子字符串
    public boolean repeatedSubstringPattern(String s) {
        int[] next=new int[s.length()];
        //获取next数组
        getNext(next,s);
        int maxLength=next[s.length()-1];
        return maxLength>0&&s.length() % (s.length() - maxLength) == 0;
    }

    public void getNext(int[] next,String needle){
        //赋初始值
        int j=0;
        
        for(int i=1;i<needle.length();i++){
            //若前后缀判断不等，则j向前移动
            while(j>0&&needle.charAt(i)!=needle.charAt(j))j=next[j-1];

            if(needle.charAt(i)==needle.charAt(j))j++;
            
            //j也等于相同前后缀的长度
            next[i]=j;
        }
    }
}