3

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?

Mike 'Pomax' Kamermans
  • 49,297
  • 16
  • 112
  • 153
Simd
  • 19,447
  • 42
  • 136
  • 271
  • take a look at this [question](http://stackoverflow.com/questions/11090289/find-longest-repetitive-sequence-in-a-string) i think you're looking for something similar? also, the complexity given of this method is O(n) so, it should be pretty fast as per your requirement. – Mridul Kashyap Jul 27 '16 at 08:44
  • @MridulKashyap My question is much simpler as my repetitions start at the beginning of the string and don't have any gaps in between them. – Simd Jul 27 '16 at 08:45

5 Answers5

4

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))
Aran-Fey
  • 39,665
  • 11
  • 104
  • 149
1

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']
AdrienW
  • 3,092
  • 6
  • 29
  • 59
0

The approach i would use:

import re

L = "hellohellohello"
N = "good"
N = "wherewhere"

cnt = 0
result = ''
for i in range(1,len(L)+1):
    if cnt <= len(re.findall(L[0:i],L)):
        cnt = len(re.findall(L[0:i],L))
        result = re.findall(L[0:i],L)[0]

print(result)

Gives the following outputs with the corresponding variable:

hello
good
where
Gábor Erdős
  • 3,599
  • 4
  • 24
  • 56
0

Assuming that the length of the repeated word is longer than 1 this would work:

a = "hellohellohello"

def splitstring(string):
    for number in range(1, len(string)):
        if string[:number] == string[number:number+number]:
            return string[:number]
    #in case there is no repetition
    return string

splitstring(a)
pawelty
  • 1,000
  • 8
  • 27
0
#_*_ coding:utf-8 _*_
import re
'''
refer to the code of Gábor Erds below
'''

N = "wherewhere"
cnt = 0
result = ''
countN = 0
showresult = []

for i in range(1,len(N)+1):
    if cnt <= len(re.findall(N[0:i],N)):
        cnt = len(re.findall(N[0:i],N))
        result = re.findall(N[0:i],N)[0]
        countN = len(N)/len(result)
for i in range(0,countN):
    showresult.append(result)
print showresult
Fan.Dog
  • 1