459.重复的子字符串

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

示例 1:

1
2
3
4
5
输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。

Solution

一个原理，将字符串s复制一次，创建一个新的字符串T=s+s，然后去掉T的第一个和最后一个字符，如果s仍然是T的子串，那么说明s是重复的子字符串构成

子串匹配用KMP算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public boolean repeatedSubstringPattern(String s) {
           String x=s+s;
           
           return KMP(x,s);

    }
    public boolean KMP(String S,String T){
        int i=1;
        int j=0;
        int []a=new int[T.length()+1];
        Next(T,a);
        while(i<S.length()-1&&j<=T.length()){
            if(j==-1||S.charAt(i)==T.charAt(j)){
                     i++;
                     j++;
            }else{
               j=a[j];
            }
            if(j==T.length()){
            return true;
        }
        }
       
        return false;
       
    }

    public void Next(String m,int []next){
        int k=-1;
        int j=0;
        next[0]=-1;
        while(j<m.length()){
             if(k==-1||m.charAt(j)==m.charAt(k)){
                 j++;
                 k++;
                 next[j]=k;
             }else{
                 k=next[k];
             }
        }
       
    }
}