How do you find a repeated substring in a string python?

Question

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

Read

Discuss

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

How do you find a repeating substring in a string Python?

(1) First generate the possible sub-strings you want to search in each string. Is there a min or max length? Build a list or set of sub-strings from the input string. (2) Once you have the sub-strings to search for, try to identify the unique locations within the input string where the substrings appear.

How do you find a repeated substring in a string?

Under these assumptions, the algorithm is as follows:.

Let the input string be denoted as inputString ..

Calculate the KMP failure function array for the input string. ... .

Let len = inputString. ... .

If it turns out that every consecutive non-overlapping substring is the same, then the answer would be = inputString..

programming python Duplicate string Python Substring Python leetcode

How do you find a repeated substring in a string python?

How do you find a repeating substring in a string Python?

How do you find a repeated substring in a string?

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội