26
votes

I have a simple problem, but can't come with a simple solution :)

Let's say I have a string. I want to detect if there is a repetition in it.

I'd like:

"blablabla" # => (bla, 3)

"rablabla"  # => (bla, 2)

The thing is I don't know what pattern I am searching for (I don't have "bla" as input).

Any idea?

EDIT:
Seeing the comments, I think I should precise a bit more what I have in mind:

  • In a string, there is either a pattern that is repeted or not.
  • The repeted pattern can be of any length.

If there is a pattern, it would be repeted over and over again until the end. But the string can end in the middle of the pattern.

Example:

"testblblblblb" # => ("bl",4) 
1
Doesn't sound like a very simple problem to me - Hubro
I'd say rablabla should return ('abl', 2), don't you? - Tim Pietzcker
And I meant simple problem to understand :) - jlengrand
Do you allow overlapping matches (e.g. the two abas in ababa)? - NPE
This is probably not the best way to solve Euler #26. You'll have to use the decimal module to handle arbitrary-precision numbers (or some equivalent approach) because 1/19 ~ 0.05263157894736842 as a float, so its repeating part doesn't even fit in a float. Admittedly you can bound the length of the repeating part, so you can make it work, but there are "mathier" ways to do it. - DSM

1 Answers

42
votes
import re
def repetitions(s):
   r = re.compile(r"(.+?)\1+")
   for match in r.finditer(s):
       yield (match.group(1), len(match.group(0))/len(match.group(1)))

finds all non-overlapping repeating matches, using the shortest possible unit of repetition:

>>> list(repetitions("blablabla"))
[('bla', 3)]
>>> list(repetitions("rablabla"))
[('abl', 2)]
>>> list(repetitions("aaaaa"))
[('a', 5)]
>>> list(repetitions("aaaaablablabla"))
[('a', 5), ('bla', 3)]