【LeetCode-简单题KMP】459. 重复的子字符串

题目

方法一：移动匹配

class Solution {
    //移动匹配
    public boolean repeatedSubstringPattern(String s) {
        StringBuffer str = new StringBuffer(s);//abab
        str.append(s);//拼接一份自己  abababab
        str.delete(0,1);// bababab
        str.delete(str.length()-1,str.length());//bababa
        //删除第一个字符和最后一个字符，不然在str里面匹配s时  直接就能从开头匹配就没有意义了
        //我们要的就是拼接起来的部分  也能匹配到原来的s
        if(str.toString().contains(s)) return true; // str: bababa   s: abab
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

方法二：KMP算法

关键代码
参考视频讲解字符串这么玩，可有点难度！ | LeetCode：459.重复的子字符串
参考题解：459.重复的子字符串—KMP解法

 // 最后判断是否是重复的子字符串，这里 next[len-1] 即代表next数组末尾的值
      if (next[len - 1] != 0 && len % (len - (next[len - 1])) == 0) {
            return true;
        }
        return false;
1
2
3
4
5

class Solution {
    //KMP算法
    public boolean repeatedSubstringPattern(String s) {
    if (s.length() == 0)   return false;
      int[] next = getNext(s);
      int len = s.length();
       // 最后判断是否是重复的子字符串，这里 next[len-1] 即代表next数组末尾的值
      if (next[len - 1] != 0 && len % (len - (next[len - 1])) == 0) {
            return true;
        }
        return false;
    }
    public int[] getNext(String s){
        int[] next = new int[s.length()];
        int j = 0;
        next[0]=j;
        for(int i = 1 ; i<next.length;i++){
            while(j> 0 && s.charAt(i) !=s.charAt(j)){
                j = next[j-1];
            }
            if(s.charAt(i) ==s.charAt(j)) j++;
            next[i] = j;
        }
        return next;
    }
}
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