【Leetcode-字符串】重复的子字符串

【Leetcode-字符串】重复的子字符串

重复的子字符串
难度：简单

判断一个字符串是否存在一个子串重复构成，那么需要满足以下两点：
1、字符串以该子串开头
2、子串的长度是字符串长度的正因数（也就是能被整除）

代码如下：

	public static int countSegments(String s) {
        if (s.length()==1){
            return false;
        }
        for (int i = 1; i <= s.length()/2; i++) {
        	//判断子串长度能否被整除
            if (s.length()%i!=0){
                continue;
            }
            String substr = s.substring(0, i);
            StringBuilder sb = new StringBuilder();
            while(!sb.toString().equals(s)){
                sb.append(substr);
                if (!s.startsWith(sb.toString())){
                    break;
                }
            }
            if (sb.toString().equals(s)){
                return true;
            }
        }
        return false;
    }

执行结果：通过

执行用时击败5.05%的用户…
题解针对我这种思路有个比较高效的判断子串是否满足条件的方法。
假设我们在判断长度为3的子串是否满足条件时，只需要依次判断第0、3、6…位，第1、4、7…位、第2、5、8位上的字符是否相等即可

代码如下：

	public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i <= n/2; ++i) {
            if (n % i == 0) {
                boolean match = true;
                for (int j = i; j < n; ++j) {
                    if (s.charAt(j) != s.charAt(j - i)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }

执行用时优化了很多，当然我也在题解中看到更棒的思路：
如果字符串 S 包含一个重复的子字符串，那么这意味着可以多次 “移位和换行”`字符串，并使其与原始字符串匹配。

例如：abcabc

移位一次：cabcab
移位两次：bcabca
移位三次：abcabc

现在字符串和原字符串匹配了，所以可以得出结论存在重复的子串。

基于这个思想，可以每次移动k个字符，直到匹配移动 length - 1 次。但是这样对于重复字符串很长的字符串，效率会非常低。在 LeetCode 中执行时间超时了。

为了避免这种无用的环绕，可以创建一个新的字符串 str，它等于原来的字符串 S 再加上 S 自身，这样其实就包含了所有移动的字符串。

比如字符串：S = acd，那么 str = S + S = acdacd

acd 移动的可能：dac、cda。其实都包含在了 str 中了。就像一个滑动窗口
所以可以直接判断 str 中去除首尾元素之后，是否包含自身元素。如果包含。则表明存在重复子串。

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