# Leetcode 459 - Repeated substring pattern

Note:

• Recursion method:

• In a for loop, from 0 to len - 1, constantly check if as the current substr(0, i), if we can exhaust the whole string.
• KMP method

• Didn’t see that someone would use kmp on an easy question jezz..
• Generate the next[].
• If there is a substr such abcd, we will have something like abcd,abcd,...,abcd.
• KMP:

• If the pattern is like abcd,abcd,...,abcd, then len - next[len - 1] === len(repeatedStr).
• The condition len % (len - (next[len - 1])) == 0 must be met as well:
• Explain: abcd,ef,abcd. When there are some extra chars in betweem, there is no way that len is divisible by len - (next[len - 1]).

Question:

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Example:

Code:

O(n)