## The Question :

*356 people think this question is useful*

I’m looking for a way to test whether or not a given string repeats itself for the entire string or not.

Examples:

[
'0045662100456621004566210045662100456621', # '00456621'
'0072992700729927007299270072992700729927', # '00729927'
'001443001443001443001443001443001443001443', # '001443'
'037037037037037037037037037037037037037037037', # '037'
'047619047619047619047619047619047619047619', # '047619'
'002457002457002457002457002457002457002457', # '002457'
'001221001221001221001221001221001221001221', # '001221'
'001230012300123001230012300123001230012300123', # '00123'
'0013947001394700139470013947001394700139470013947', # '0013947'
'001001001001001001001001001001001001001001001001001', # '001'
'001406469760900140646976090014064697609', # '0014064697609'
]

are strings which repeat themselves, and

[
'004608294930875576036866359447',
'00469483568075117370892018779342723',
'004739336492890995260663507109',
'001508295625942684766214177978883861236802413273',
'007518796992481203',
'0071942446043165467625899280575539568345323741',
'0434782608695652173913',
'0344827586206896551724137931',
'002481389578163771712158808933',
'002932551319648093841642228739',
'0035587188612099644128113879',
'003484320557491289198606271777',
'00115074798619102416570771',
]

are examples of ones that do not.

The repeating sections of the strings I’m given can be quite long, and the strings themselves can be 500 or more characters, so looping through each character trying to build a pattern then checking the pattern vs the rest of the string seems awful slow. Multiply that by potentially hundreds of strings and I can’t see any intuitive solution.

I’ve looked into regexes a bit and they seem good for when you know what you’re looking for, or at least the length of the pattern you’re looking for. Unfortunately, I know neither.

How can I tell if a string is repeating itself and if it is, what the shortest repeating subsequence is?

*The Question Comments :*

## The Answer 1

*580 people think this answer is useful*

Here’s a concise solution which avoids regular expressions and slow in-Python loops:

def principal_period(s):
i = (s+s).find(s, 1, -1)
return None if i == -1 else s[:i]

See the Community Wiki answer started by @davidism for benchmark results. In summary,

David Zhang’s solution is the clear winner, outperforming all others by at least 5x for the large example set.

(That answer’s words, not mine.)

This is based on the observation that a string is periodic if and only if it is equal to a nontrivial rotation of itself. Kudos to @AleksiTorhamo for realizing that we can then recover the principal period from the index of the first occurrence of `s`

in `(s+s)[1:-1]`

, and for informing me of the optional `start`

and `end`

arguments of Python’s `string.find`

.

## The Answer 2

*183 people think this answer is useful*

Here’s a solution using regular expressions.

import re
REPEATER = re.compile(r"(.+?)\1+$")
def repeated(s):
match = REPEATER.match(s)
return match.group(1) if match else None

Iterating over the examples in the question:

examples = [
'0045662100456621004566210045662100456621',
'0072992700729927007299270072992700729927',
'001443001443001443001443001443001443001443',
'037037037037037037037037037037037037037037037',
'047619047619047619047619047619047619047619',
'002457002457002457002457002457002457002457',
'001221001221001221001221001221001221001221',
'001230012300123001230012300123001230012300123',
'0013947001394700139470013947001394700139470013947',
'001001001001001001001001001001001001001001001001001',
'001406469760900140646976090014064697609',
'004608294930875576036866359447',
'00469483568075117370892018779342723',
'004739336492890995260663507109',
'001508295625942684766214177978883861236802413273',
'007518796992481203',
'0071942446043165467625899280575539568345323741',
'0434782608695652173913',
'0344827586206896551724137931',
'002481389578163771712158808933',
'002932551319648093841642228739',
'0035587188612099644128113879',
'003484320557491289198606271777',
'00115074798619102416570771',
]
for e in examples:
sub = repeated(e)
if sub:
print("%r: %r" % (e, sub))
else:
print("%r does not repeat." % e)

… produces this output:

'0045662100456621004566210045662100456621': '00456621'
'0072992700729927007299270072992700729927': '00729927'
'001443001443001443001443001443001443001443': '001443'
'037037037037037037037037037037037037037037037': '037'
'047619047619047619047619047619047619047619': '047619'
'002457002457002457002457002457002457002457': '002457'
'001221001221001221001221001221001221001221': '001221'
'001230012300123001230012300123001230012300123': '00123'
'0013947001394700139470013947001394700139470013947': '0013947'
'001001001001001001001001001001001001001001001001001': '001'
'001406469760900140646976090014064697609': '0014064697609'
'004608294930875576036866359447' does not repeat.
'00469483568075117370892018779342723' does not repeat.
'004739336492890995260663507109' does not repeat.
'001508295625942684766214177978883861236802413273' does not repeat.
'007518796992481203' does not repeat.
'0071942446043165467625899280575539568345323741' does not repeat.
'0434782608695652173913' does not repeat.
'0344827586206896551724137931' does not repeat.
'002481389578163771712158808933' does not repeat.
'002932551319648093841642228739' does not repeat.
'0035587188612099644128113879' does not repeat.
'003484320557491289198606271777' does not repeat.
'00115074798619102416570771' does not repeat.

The regular expression `(.+?)\1+$`

is divided into three parts:

`(.+?)`

is a matching group containing at least one (but as few as possible) of any character (because `+?`

is non-greedy).

`\1+`

checks for at least one repetition of the matching group in the first part.

`$`

checks for the end of the string, to ensure that there’s no extra, non-repeating content after the repeated substrings (and using `re.match()`

ensures that there’s no non-repeating text *before* the repeated substrings).

In Python 3.4 and later, you could drop the `$`

and use `re.fullmatch()`

instead, or (in any Python at least as far back as 2.3) go the other way and use `re.search()`

with the regex `^(.+?)\1+$`

, all of which are more down to personal taste than anything else.

## The Answer 3

*90 people think this answer is useful*

You can make the observation that for a string to be considered repeating, its length must be divisible by the length of its repeated sequence. Given that, here is a solution that generates divisors of the length from `1`

to `n / 2`

inclusive, divides the original string into substrings with the length of the divisors, and tests the equality of the result set:

from math import sqrt, floor
def divquot(n):
if n > 1:
yield 1, n
swapped = []
for d in range(2, int(floor(sqrt(n))) + 1):
q, r = divmod(n, d)
if r == 0:
yield d, q
swapped.append((q, d))
while swapped:
yield swapped.pop()
def repeats(s):
n = len(s)
for d, q in divquot(n):
sl = s[0:d]
if sl * q == s:
return sl
return None

**EDIT:** In Python 3, the `/`

operator has changed to do float division by default. To get the `int`

division from Python 2, you can use the `//`

operator instead. Thank you to @TigerhawkT3 for bringing this to my attention.

The `//`

operator performs integer division in both Python 2 and Python 3, so I’ve updated the answer to support both versions. The part where we test to see if all the substrings are equal is now a short-circuiting operation using `all`

and a generator expression.

**UPDATE:** In response to a change in the original question, the code has now been updated to return the smallest repeating substring if it exists and `None`

if it does not. @godlygeek has suggested using `divmod`

to reduce the number of iterations on the `divisors`

generator, and the code has been updated to match that as well. It now returns all positive divisors of `n`

in ascending order, exclusive of `n`

itself.

**Further update for high performance:** After multiple tests, I’ve come to the conclusion that simply testing for string equality has the best performance out of any slicing or iterator solution in Python. Thus, I’ve taken a leaf out of @TigerhawkT3 ‘s book and updated my solution. It’s now over 6x as fast as before, noticably faster than Tigerhawk’s solution but slower than David’s.

## The Answer 4

*88 people think this answer is useful*

Here are some benchmarks for the various answers to this question. There were some surprising results, including wildly different performance depending on the string being tested.

Some functions were modified to work with Python 3 (mainly by replacing `/`

with `//`

to ensure integer division). If you see something wrong, want to add your function, or want to add another test string, ping @ZeroPiraeus in the Python chatroom.

In summary: there’s about a 50x difference between the best- and worst-performing solutions for the large set of example data supplied by OP here (via this comment). David Zhang’s solution is the clear winner, outperforming all others by around 5x for the large example set.

A couple of the answers are *very* slow in extremely large “no match” cases. Otherwise, the functions seem to be equally matched or clear winners depending on the test.

Here are the results, including plots made using matplotlib and seaborn to show the different distributions:

**Corpus 1 (supplied examples – small set)**

mean performance:
0.0003 david_zhang
0.0009 zero
0.0013 antti
0.0013 tigerhawk_2
0.0015 carpetpython
0.0029 tigerhawk_1
0.0031 davidism
0.0035 saksham
0.0046 shashank
0.0052 riad
0.0056 piotr
median performance:
0.0003 david_zhang
0.0008 zero
0.0013 antti
0.0013 tigerhawk_2
0.0014 carpetpython
0.0027 tigerhawk_1
0.0031 davidism
0.0038 saksham
0.0044 shashank
0.0054 riad
0.0058 piotr

**Corpus 2 (supplied examples – large set)**

mean performance:
0.0006 david_zhang
0.0036 tigerhawk_2
0.0036 antti
0.0037 zero
0.0039 carpetpython
0.0052 shashank
0.0056 piotr
0.0066 davidism
0.0120 tigerhawk_1
0.0177 riad
0.0283 saksham
median performance:
0.0004 david_zhang
0.0018 zero
0.0022 tigerhawk_2
0.0022 antti
0.0024 carpetpython
0.0043 davidism
0.0049 shashank
0.0055 piotr
0.0061 tigerhawk_1
0.0077 riad
0.0109 saksham

**Corpus 3 (edge cases)**

mean performance:
0.0123 shashank
0.0375 david_zhang
0.0376 piotr
0.0394 carpetpython
0.0479 antti
0.0488 tigerhawk_2
0.2269 tigerhawk_1
0.2336 davidism
0.7239 saksham
3.6265 zero
6.0111 riad
median performance:
0.0107 tigerhawk_2
0.0108 antti
0.0109 carpetpython
0.0135 david_zhang
0.0137 tigerhawk_1
0.0150 shashank
0.0229 saksham
0.0255 piotr
0.0721 davidism
0.1080 zero
1.8539 riad

The tests and raw results are available here.

## The Answer 5

*37 people think this answer is useful*

Non-regex solution:

def repeat(string):
for i in range(1, len(string)//2+1):
if not len(string)%len(string[0:i]) and string[0:i]*(len(string)//len(string[0:i])) == string:
return string[0:i]

Faster non-regex solution, thanks to @ThatWeirdo (see comments):

def repeat(string):
l = len(string)
for i in range(1, len(string)//2+1):
if l%i: continue
s = string[0:i]
if s*(l//i) == string:
return s

The above solution is very rarely slower than the original by a few percent, but it’s usually a good bit faster – sometimes a whole lot faster. It’s still not faster than davidism’s for longer strings, and zero’s regex solution is superior for short strings. It comes out to the fastest (according to davidism’s test on github – see his answer) with strings of about 1000-1500 characters. Regardless, it’s reliably second-fastest (or better) in all cases I tested. Thanks, ThatWeirdo.

Test:

print(repeat('009009009'))
print(repeat('254725472547'))
print(repeat('abcdeabcdeabcdeabcde'))
print(repeat('abcdefg'))
print(repeat('09099099909999'))
print(repeat('02589675192'))

Results:

009
2547
abcde
None
None
None

## The Answer 6

*24 people think this answer is useful*

First, halve the string as long as it’s a “2 part” duplicate. This reduces the search space if there are an even number of repeats. Then, working forwards to find the smallest repeating string, check if splitting the full string by increasingly larger sub-string results in only empty values. Only sub-strings up to `length // 2`

need to be tested since anything over that would have no repeats.

def shortest_repeat(orig_value):
if not orig_value:
return None
value = orig_value
while True:
len_half = len(value) // 2
first_half = value[:len_half]
if first_half != value[len_half:]:
break
value = first_half
len_value = len(value)
split = value.split
for i in (i for i in range(1, len_value // 2) if len_value % i == 0):
if not any(split(value[:i])):
return value[:i]
return value if value != orig_value else None

This returns the shortest match or None if there is no match.

## The Answer 7

*16 people think this answer is useful*

The problem may also be solved in `O(n)`

in worst case with prefix function.

Note, it may be slower in general case(UPD: and is much slower) than other solutions which depend on number of divisors of `n`

, but usually find fails sooner, I think one of bad cases for them will be `aaa....aab`

, where there are `n - 1 = 2 * 3 * 5 * 7 ... *p_n - 1`

`a`

‘s

First of all you need to calculate prefix function

def prefix_function(s):
n = len(s)
pi = [0] * n
for i in xrange(1, n):
j = pi[i - 1]
while(j > 0 and s[i] != s[j]):
j = pi[j - 1]
if (s[i] == s[j]):
j += 1
pi[i] = j;
return pi

then either there’s no answer or the shortest period is

k = len(s) - prefix_function(s[-1])

and you just have to check if `k != n and n % k == 0`

(if `k != n and n % k == 0`

then answer is `s[:k]`

, else there’s no answer

You may check the proof here (in Russian, but online translator will probably do the trick)

def riad(s):
n = len(s)
pi = [0] * n
for i in xrange(1, n):
j = pi[i - 1]
while(j > 0 and s[i] != s[j]):
j = pi[j - 1]
if (s[i] == s[j]):
j += 1
pi[i] = j;
k = n - pi[-1]
return s[:k] if (n != k and n % k == 0) else None

## The Answer 8

*16 people think this answer is useful*

This version tries only those candidate sequence lengths that are factors of the string length; and uses the `*`

operator to build a full-length string from the candidate sequence:

def get_shortest_repeat(string):
length = len(string)
for i in range(1, length // 2 + 1):
if length % i: # skip non-factors early
continue
candidate = string[:i]
if string == candidate * (length // i):
return candidate
return None

Thanks to TigerhawkT3 for noticing that `length // 2`

without `+ 1`

would fail to match the `abab`

case.

## The Answer 9

*15 people think this answer is useful*

Here’s a straight forward solution, without regexes.

For substrings of `s`

starting from zeroth index, of lengths 1 through `len(s)`

, check if that substring, `substr`

is the repeated pattern. This check can be performed by concatenating `substr`

with itself `ratio`

times, such that the length of the string thus formed is equal to the length of `s`

. Hence `ratio=len(s)/len(substr)`

.

Return when first such substring is found. This would provide the smallest possible substring, if one exists.

def check_repeat(s):
for i in range(1, len(s)):
substr = s[:i]
ratio = len(s)/len(substr)
if substr * ratio == s:
print 'Repeating on "%s"' % substr
return
print 'Non repeating'
>>> check_repeat('254725472547')
Repeating on "2547"
>>> check_repeat('abcdeabcdeabcdeabcde')
Repeating on "abcde"

## The Answer 10

*9 people think this answer is useful*

I started with more than eight solutions to this problem. Some were bases on regex (match, findall, split), some of string slicing and testing, and some with string methods (find, count, split). Each had benefits in code clarity, code size, speed and memory consumption. I was going to post my answer here when I noticed that execution speed was ranked as important, so I did more testing and improvement to arrive at this:

def repeating(s):
size = len(s)
incr = size % 2 + 1
for n in xrange(1, size//2+1, incr):
if size % n == 0:
if s[:n] * (size//n) == s:
return s[:n]

This answer seems similar to a few other answers here, but it has a few speed optimisations others have not used:

`xrange`

is a little faster in this application,
- if an input string is an odd length, do not check any even length substrings,
- by using
`s[:n]`

directly, we avoid creating a variable in each loop.

I would be interested to see how this performs in the standard tests with common hardware. I believe it will be well short of David Zhang’s excellent algorithm in most tests, but should be quite fast otherwise.

I found this problem to be very counter-intuitive. The solutions I thought would be fast were slow. The solutions that looked slow were fast! It seems that Python’s string creation with the multiply operator and string comparisons are highly optimised.

## The Answer 11

*2 people think this answer is useful*

This function runs very quickly (tested and it’s over 3 times faster than fastest solution here on strings with over 100k characters and the difference gets bigger the longer the repeating pattern is). It tries to minimise the number of comparisons needed to get the answer:

def repeats(string):
n = len(string)
tried = set([])
best = None
nums = [i for i in xrange(2, int(n**0.5) + 1) if n % i == 0]
nums = [n/i for i in nums if n/i!=i] + list(reversed(nums)) + [1]
for s in nums:
if all(t%s for t in tried):
print 'Trying repeating string of length:', s
if string[:s]*(n/s)==string:
best = s
else:
tried.add(s)
if best:
return string[:best]

Note that for example for string of length 8 it checks only fragment of size 4 and it does not have to test further because pattern of length 1 or 2 would result in repeating pattern of length 4:

>>> repeats('12345678')
Trying repeating string of length: 4
None
# for this one we need only 2 checks
>>> repeats('1234567812345678')
Trying repeating string of length: 8
Trying repeating string of length: 4
'12345678'

## The Answer 12

*0 people think this answer is useful*

In David Zhang’s answer if we have some sort of circular buffer this will not work: `principal_period('6210045662100456621004566210045662100456621')`

due to the starting `621`

, where I would have liked it to spit out: `00456621`

.

Extending his solution we can use the following:

def principal_period(s):
for j in range(int(len(s)/2)):
idx = (s[j:]+s[j:]).find(s[j:], 1, -1)
if idx != -1:
# Make sure that the first substring is part of pattern
if s[:j] == s[j:][:idx][-j:]:
break
return None if idx == -1 else s[j:][:idx]
principal_period('6210045662100456621004566210045662100456621')
>>> '00456621'

## The Answer 13

*-1 people think this answer is useful*

*Here is the code in python that checks for repetition of sub string in the main string given by the user*.

print "Enter a string...."
#mainstring = String given by user
mainstring=raw_input(">")
if(mainstring==''):
print "Invalid string"
exit()
#charlist = Character list of mainstring
charlist=list(mainstring)
strarr=''
print "Length of your string :",len(mainstring)
for i in range(0,len(mainstring)):
strarr=strarr+charlist[i]
splitlist=mainstring.split(strarr)
count = 0
for j in splitlist:
if j =='':
count+=1
if count == len(splitlist):
break
if count == len(splitlist):
if count == 2:
print "No repeating Sub-String found in string %r"%(mainstring)
else:
print "Sub-String %r repeats in string %r"%(strarr,mainstring)
else :
print "No repeating Sub-String found in string %r"%(mainstring)

*Input*:

0045662100456621004566210045662100456621

*Output* :

Length of your string : 40

Sub-String ‘00456621’ repeats in string ‘0045662100456621004566210045662100456621’

*Input* :

004608294930875576036866359447

*Output*:

Length of your string : 30

No repeating Sub-String found in string ‘004608294930875576036866359447’