### Description:

Given a non-empty string check if it can be constructed by taking a sub-string of it and appending multiple copies of the sub-string 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:TrueExplanation:It's the sub-string "ab" twice.

**Example 2:**

Input:"aba"Output:False

**Example 3:**

Input:"abcabcabcabc"Output:TrueExplanation:It's the sub-string "abc" four times. (And the sub-string "abcabc" twice.)

### Solution 1:

```
# https://leetcode.com/problems/repeated-substring-pattern/
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
length = len(s)
if (not length):
return False
mid = length // 2
stack = list()
for char in s[:mid + 1]:
if (not stack):
stack.append(char)
else:
# if length of string is not multiple
# length of sub-string skip
if (length % len(stack) != 0):
stack.append(char)
continue
# if current letter and first letter of the
# sub-string don't match, then skip to the next letter
if (not stack[0] == char):
stack.append(char)
else:
status = self.checkRepetetion(s[len(stack):], stack)
if (status):
return True
stack.append(char)
return False
def checkRepetetion(self, s, snip):
if (s and ''.join(snip) == s[:len(snip)]):
s = s[len(snip):]
else:
return False
# If string becomes empty
if (not s):
return True
return self.checkRepetetion(s, snip)
```

### Explanation:

Our objective is to find out whether the given string can be formed by repeating any one of its sub-strings. In the first example given in the description, the string **s** is *'abab'. *This can be formed by repeating its sub-string *'ab'. *There may be multiple ways in which we can achieve this. The most crude way to do this is by brute force.

i.e. for every sub-string possible, check whether we can generate the complete string by repeating it. The steps in solving this for the example 1 are as follows,

- step 1: Take the first smallest prefix. i.e.
*'a'* - Step 2: Check whether we can generate the original string by repeating it. We can achieve this by popping the matched character from the beginning of the string, repeatedly.
- Step 3: If no string left after completing sub-string match, then return True.
- Step 4: Take the next smallest prefix possible and repeat from step 2...

This algorithm takes O(n^{2}) in the worst case scenario. If we observe the problem very closely, there is a pattern that we can use to identify the repeated sub-string pattern that makes the given string. Assume that the string **s **formed by repeating a sub-string pattern Sp twice. i.e. s = SpSp.

Then s + s = ss = SpSpSpSp. Here if we deform the start and end patterns,

i.e. SmSpSpSm. If we are able to find string 's' in the result, then the answer is *'True'* else *'False'. *This implementation has worst case complexity as O(n) and we can implement it with in two lines of code.

### Solution 2 (Best Solution):

```
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
s_twice = s + s
if(s in s_twice[1:-1]):
return True
return False
```