> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/string/kmp/459-repeated-substring-pattern.md).

# 459 Repeated Substring Pattern

## 459. [Repeated Substring Pattern](https://leetcode.com/problems/repeated-substring-pattern/description/)

## 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**

```java
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构成

```java
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)