How to split repeated strings into list

Question

I have strings each of which is one or more copies of some string. For example:

L = "hellohellohello"
M = "good"
N = "wherewhere"
O = "antant"

I would like to split such strings into a list so that each element just has the part that was repeated. For example:

splitstring(L) ---> ["hello", "hello", "hello"]
splitstring(M) ---> ["good"]
splitstring(N) ---> ["where", "where"]
splitstring(O) ---> ["ant", "ant"]

As the strings are each about 1000 characters long it would be great if this was reasonably fast as well.

Note that in my case the repetitions all start at the start of the string and have no gaps in between them so it's much simpler than the general problem of finding maximal repetitions in a string.

How can one do this?

Answer 1

Using regex to find the repeating word, then simply creating a list of the appropriate length:

def splitstring(string):
    match= re.match(r'(.*?)(?:\1)*$', string)
    word= match.group(1)
    return [word] * (len(string)//len(word))

Answer 2

Try this. Instead of cutting your list, it concentrates on finding the shortest pattern, then just creates a new list by repeating this pattern an appropriate number of times.

def splitstring(s):
    # searching the number of characters to split on
    proposed_pattern = s[0]
    for i, c in enumerate(s[1:], 1):
        if proposed_pattern == s[i:(i+len(proposed_pattern))]:
            # found it
            break
        else:
            proposed_pattern += c
    else:
        print 'found no pattern'
        exit(1)
    # generating the list
    n = len(proposed_pattern)
    return [proposed_pattern]*(len(s)//n)


if __name__ == '__main__':
    L = 'hellohellohellohello'
    print splitstring(L)  # prints ['hello', 'hello', 'hello', 'hello']