【KMP】【判断是否是重复子字符串】Leetcode 459 重复的子字符串

- 解法1 拼接字符串-掐头去尾后判断是否含有原字符串
- 解法2 KMP——重复子串的最小单位是这个字符串里的最长相等前后缀所不包含的子串
- 解法3 暴力解法
- - KMP

---------------🎈🎈题目链接🎈🎈-------------------

在这里插入图片描述

解法1 拼接字符串-掐头去尾后判断是否含有原字符串

判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。
注意：要除去 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s。

时间复杂度O(M+N) 调用contains方法时间复杂度
空间复杂度O(1)

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

解法2 KMP——重复子串的最小单位是这个字符串里的最长相等前后缀所不包含的子串

如果这个字符串s是由重复子串组成的，
那么
重复子串的最小单位就是这个字符串里的最长相等前后缀所不包含的子串组成的
在这里插入图片描述

时间复杂度O(N)
空间复杂度O(N)

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if(s.length() == 1) return false;
        int[] next = new int[s.length()];
        getNext(next,s);
		
		// 如果next表的最后一个值大于零 且 s的长度可以被 s的长度-next表的最后一个值 整除 则return true
        if(next[s.length()-1]>0 && (s.length() % (s.length() -next[s.length()-1])==0)) {
            return true;
        }
        else{
            return false;
        }
    }

    // 获取next数组
    public void getNext(int[] next, String s){
        int i = 0; //前缀末尾 也等于包含i的之前字符串的最长相等前后缀长度
        int j = 1; //后缀末尾
        next[0] = 0;
        for(; j<s.length(); j++){
            while(i > 0 && s.charAt(i) != s.charAt(j)){ //如果不相同，那么前缀i就回退到next[i-1]
                i = next[i-1];
            }
            if(s.charAt(i) == s.charAt(j)){ // 如果相同 那么前缀i就++
                i++;
            }
            // 更新next数组
            next[j] = i;
        }
    }
}

解法3 暴力解法

时间复杂度：O(n^2)，其中 n 为字符串 s 的长度。
空间复杂度：O(1)。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
      // 暴力做法 外层循环子串的结束位置 内层左匹配
        for(int i = 0; i<s.length()/2; i++){
          if(s.length() % (i+1) ==0){
            int count = s.length() /(i+1);
            int j = 1;
            for(; j < count; j++){
              System.out.println(s.substring(0, i+1));
              System.out.println(s.substring((i+1)*j, (i+1) * (j+1)));
              if(!s.substring(0, i+1).equals(s.substring((i+1)*j, (i+1) * (j+1)))) break;
            }
            if(j==count) return true;
          } 
        }
        return false;
        
    }
}