Start by building a prefix array.
Loop through it in reverse and stop the first time you find something that's repeated in your string [that is, it has a str.count[]>1
.
Now if the same substring exists right next to itself, you can return it as the word you're looking for, however you must take into consideration the 'appleappl'
example, where the proposed algorithm would return appl
. For that, when you find a substring that exists more than once in your string,
you return as a result that substring plus whatever is between its next occurence, namely for 'appleappl'
you return 'appl' +'e' = 'apple'
. If no such strings are found, you return the whole word since there are no repetitions.
def repeat[s]:
prefix_array=[]
for i in range[len[s]]:
prefix_array.append[s[:i]]
#see what it holds to give you a better picture
print prefix_array
#stop at 1st element to avoid checking for the ' ' char
for i in prefix_array[:1:-1]:
if s.count[i] > 1 :
#find where the next repetition starts
offset = s[len[i]:].find[i]
return s[:len[i]+offset]
break
return s
print repeat[s]
View Discussion
Improve Article
Save Article
View Discussion
Improve Article
Save Article
While working with strings, many times, we can come across a use case in which we need to find if a string has in it the repeating substring, which repeats all over the string and thus making a multiple of the root substring. Let’s discuss certain ways in which we can get the root substring of string.
Method #1 : Using List comprehension + Brute Force
We can perform this task using selective slicing and brute force manner. This is the naive method to find the string in which we try to get the root string by repetitive division of string.
test_str
=
"GeeksforGeeksGeeksforGeeksGeeksforGeeks"
print
[
"The original string is : "
+
test_str]
res
=
None
for
i
in
range
[
1
,
len
[test_str]
/
/
2
+
1
]:
if
[
not
len
[test_str]
%
len
[test_str[
0
:i]]
and
test_str[
0
:i]
*
[
len
[test_str]
/
/
len
[test_str[
0
:i]]]
=
=
test_str]:
res
=
test_str[
0
:i]
print
[
"The root substring of string : "
+
res]
Output :
The original string is : GeeksforGeeksGeeksforGeeksGeeksforGeeks The root substring of string : GeeksforGeeks
Method #2 : Using list slicing + find[]
This problem can also be solved using the fact that we can search for root string after adding a string and checking the root string in this string except last and first character, represents the string is repeating itself.
Doesn’t work for string length < 2.
test_str
=
"GeeksforGeeksGeeksforGeeksGeeksforGeeks"
print
[
"The original string is : "
+
test_str]
res
=
None
temp
=
[test_str
+
test_str].find[test_str,
1
,
-
1
]
if
temp !
=
-
1
:
res
=
test_str[:temp]
print
[
"The root substring of string : "
+
res]
Output :
The original string is : GeeksforGeeksGeeksforGeeksGeeksforGeeks The root substring of string : GeeksforGeeks