459. 重复的子字符串

题目：459. 重复的子字符串

解答

package com.atlayla.LeetCode;

public class LeetCode459 {
    public static void main(String[] args) {
        String s = "abab";
        System.out.println(repeatedSubstringPattern(s));
    }

    //方法一：暴力法
    public static boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        //寻找子字符串
        for(int i = 1; i * 2 <= n; ++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;
    }
}

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

解答

方法一：暴力法

一个长度为 n的字符串 s 由 一个长度为 n’的子串 s’ 重复多次构成
1.n 一定是 n’ 的倍数；
2.s’一定是 s的前缀；
3.对于任意的 i ∈ [n’, n)，有 s[i] = s[i - n’]。
也就是说s’之后，的每一个位置上的字符 s[i]，都需要与它之前的第 n’ 个字符 s[i-n’] 相同。

所以用两次for遍历，一次用于查找子字符串，一次用于s[i]的比对。