4

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?

Improve this question
2
  • take a look at this question 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. Commented Jul 27, 2016 at 8: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. Commented Jul 27, 2016 at 8:45

5 Answers 5

Reset to default
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))
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Nice idea, I thought about doing something like that too.
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']
Improve this answer

1 Comment

I didn't know any of these 3 things, thank you sir. I will test this and edit
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
Improve this answer

Comments

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)
Improve this answer

1 Comment

It fails on "aabaab".
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
Improve this answer

1 Comment

Please add an explanation to why your code is different from Gábor Erdős's post.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.