Victor Victor - 1 year ago 167
Python Question

shortest repeated substring [PYTHON]

Is there a quick method to find the shortest repeated substring and how many times it occurs? If there is non you only need to return the actual string ( last case ).

('CT', 12)

>>> repeated('GATCGATCGATCGATC')
('GATC', 4)


Because some people think it's 'homework' I can show my efforts:

def repeated(sequentie):
string = ''

for i in sequentie:
if i not in string:
string += i

items = sequentie.count(string)
if items * len(string) == len(sequentie):
return (string, items)
return (sequentie, 1)

Answer Source

Your method unfortunately won't work, since it assumes that the repeating substring will have unique characters. This may not be the case:


You were somewhat on the right track, though. The shortest way that I can think of is to just try and check over and over if some prefix indeed makes up the entire string:

def find_shorted_substring(s):
    for i in range(1, len(s) + 1):
        substring = s[:i]
        repeats = len(s) // len(substring)

        if substring * repeats == s:
            return (substring, repeats)

It's not very efficient, but it works. There are better ways of doing it.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download