Repeating substring in a string in python

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)

Sometimes, while working with Python strings, we can have a problem in which we need to perform splitting. This can be of a custom nature. In this, we can have a split in which we need to split by all the repetitions. This can have applications in many domains. Let us discuss certain ways in which this task can be performed. 

Method #1: Using * operator + len() This is one of the way in which we can perform this task. In this, we compute the length of the repeated string and then divide the list to obtain root and construct new list using * operator. 

Python3

test_str = "gfggfggfggfggfggfggfggfg"

print("The original string is : " + test_str)

K = 'gfg'

temp = len(test_str) // len(str(K))

res = [K] * temp

print("The split string is : " + str(res))

Output : 

The original string is : gfggfggfggfggfggfggfggfg
The split string is : ['gfg', 'gfg', 'gfg', 'gfg', 'gfg', 'gfg', 'gfg', 'gfg']

  Method #2 : Using re.findall() This is yet another way in which this problem can be solved. In this, we use findall() to get all the substrings and split is also performed internally. 

Python3

import re

test_str = "gfggfggfggfggfggfggfggfg"

print("The original string is : " + test_str)

K = 'gfg'

res = re.findall(K, test_str)

print("The split string is : " + str(res))

Output : 

The original string is : gfggfggfggfggfggfggfggfg
The split string is : ['gfg', 'gfg', 'gfg', 'gfg', 'gfg', 'gfg', 'gfg', 'gfg']

Method #3 : Using count() method and * operator

Python3

test_str = "gfggfggfggfggfggfggfggfg"

print("The original string is : " + test_str)

K = 'gfg'

re=test_str.count(K)

res=[K]*re

print("The split string is : " + str(res))

Output

The original string is : gfggfggfggfggfggfggfggfg
The split string is : ['gfg', 'gfg', 'gfg', 'gfg', 'gfg', 'gfg', 'gfg', 'gfg']

The Time and Space Complexity for all the methods are the same:

Time Complexity: O(n)

Space Complexity: O(n)

In this article, we will learn how to use the inbuilt count function using examples. Then we will see how to count repeated substring in a given string in Python.

Python has a built-in function for counting the repeated substring in a given string called count(). As the name suggests, it counts the occurrence of a substring in a given string.

Python – count() function

string="abcdefghijklmnop"
string.count(substring, start_index, end_index)

The count function has 3 parameters.

1. Substring: This parameter is compulsory since it specifies the string whose occurrence is to be found.
2. Start_index: This parameter is optional. It gives the starting index of the string from which the search will begin.
3. End_index: This parameter is optional. It gives the ending index of the string where the search for substring will end.

Read: Count number of occurrences of a substring in a string in Python

Count repeated substring in a given string in Python

1. This example only contains the compulsory parameter. In this, we first define a string, then by using the count function calculate the occurrence of substring “aab” in the string defined above.

   string= "aabbcaabcbbcaabdaab"
   print(string.count("aab"))

   Output:

   4

2. This example contains compulsory as well as the optional parameters. In this, we first define a string, then by using the count function calculate the occurrence of substring “aab” in the string starting from index 2 and ending at index 15 instead of considering the whole string.

   string= "aabbcaabcbbcaabdaab"
   print(string.count("aab",2,15))

   Output:

   2

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

How do you find a repeated substring in a string?

How do you find consecutive repeated words in a string in Python?

How do you repeat a string multiple times in Python?