459 Repeated Substring Pattern

459. Repeated Substring Pattern

1. Question

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

Input: "abab"


Output: True


Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"


Output: False

Example 3:

Input: "abcabcabcabc"


Output: True

Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

2. Implementation

(1) Brute Force

class Solution {ja
    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();

        for (int i = len / 2; i >= 1; i--) {
            if (len % i == 0) {
                int parts = len / i;
                String substr = s.substring(0, i);
                StringBuilder sb = new StringBuilder();

                for (int j = 0; j < parts; j++) {
                    sb.append(substr);
                }

                if (sb.toString().equals(s)) {
                    return true;
                }
            }
        }
        return false;
    }
}

(2) KMP

思路: 利用KMP里构建lookup table的思路，在KMP里, table[i]代表i位置上，最长的前缀和后缀的共同长度，而在这里table[i]代表的是以i结束的substring的重复string的character个数。所以我们只要计算得出这个table然后查看table[table.length - 1], 如果它不为0(说明有重复substring) 且 这个重复的substring长度是 整个string 减去table[table.length - 1]代表的substring长度是的倍数，则该string可以由重复substring构成

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        int[] table = getTable(s);
        return (table[table.length - 1] != 0) && (table[table.length - 1] % (len - table[table.length - 1]) == 0);
    }

    public int[] getTable(String s) {
        int[] table = new int[s.length()];

        int index = 0;
        for (int i = 1; i < s.length();) {
            if (s.charAt(index) == s.charAt(i)) {
                table[i] = index + 1;
                ++index;
                ++i;
            }
            else if (index != 0) {
                index = table[index - 1];
            }
            else {
                table[i] = 0;
                ++i;
            }
        }
        return table;
    }
}

3. Time & Space Complexity

Brute Force: 时间复杂度O(n^2), 空间复杂度O(n)

KMP: 时间复杂度O(n), 空间复杂度O(n)