Check a string for repeated substrings

Given a string, check if it has a substring that can be used to construct the string by concatenating multiple copies of it.

For example,

 
The idea is to concatenate the input string with itself and remove the first and last characters from it. Next, search for the input string in the concatenated string; if it’s there, we can say that the string has a repeated substring. This works because the repeated substring (if it exists) would appear somewhere in the center of the string upon doubling it.

To illustrate, consider the string S, consisting of a repeated substring s, occurring n times. This can be written as follows:

S = sⁿ

 
The string S when combined with itself, creates a string SS, which can be expressed as follows:

SS = sⁿ + sⁿ
   = s^2×n
   = s + s^(2×n-2) + s

 
The repeated substring s can be written as lxr, where l and r are the leftmost and rightmost characters of s, and x forms the remaining substring. When the first and last characters of the string SS are removed, we get another string SS, which can be written as follows:

SS’ = xr + s^(2×n-2) + lx

 
Now it is evident that S exists in SS' for all n >= 2.

For n = 2, S = s² and SS’ = xr + s² + lx
For n = 3, S = s³ and SS’ = xr + s⁴ + lx
For n = 4, S = s⁴ and SS’ = xr + s⁶ + lx
For n = 5, S = s⁵ and SS’ = xr + s⁸ + lx
…
and so on.

 
Following is the C++, Java, and Python implementation based on the idea:

The time complexity of the above solution is O(n) where n is the length of the string.