shortest repeated substring [PYTHON]

Question

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 ).

>>> repeated('CTCTCTCTCTCTCTCTCTCTCTCT') 
('CT', 12)

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

>>> repeated('GATCGATCGATCGATCG')         
('GATCGATCGATCGATCG', 1)

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)
    else:
        return (sequentie, 1)

Actually it's summer break and I only want to learn something, it's a bit hard to say thinks like that... — Victor, Aug 29 '16 at 02:22
None of your examples returns the _shortest_ repeated substring. — Klaus D., Aug 29 '16 at 02:36
Welcome to SO! I don't python, but you might look into some of the language-agnostic algorithms lying around, e.g. http://stackoverflow.com/q/6021274/781965 - then ask if you run into problems implementing it. Otherwise if you want to progress with your existing efforts explain where they're failing or whatever - input, expected output, actual output. Otherwise you're likely to have a bad response on SO; the basic rule for questions is to make it as easy as possible for answerers :) — Jeff, Aug 29 '16 at 02:37
So your first block is not what you expect, but what you have? You should make that clear and add your excepted output to the question. — Klaus D., Aug 29 '16 at 02:42
First block is what i need, second block is what I tried. I'm just a beginner. — Victor, Aug 29 '16 at 02:59
Some ppl on SO relish the challenge of the question. If you are learning--- find some algo tutorials follow them. SO is also not a personal tutorial service. — Merlin, Aug 29 '16 at 05:49

score 1 · Accepted Answer · answered Aug 29 '16 at 03:18

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

abaabaabaabaabaaba

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.

shortest repeated substring [PYTHON]

1 Answers1