Find the shortest whole repetitive substring (part 3)

This is a new discussion from this post (Find the shortest whole repetitive substring) and since it is totally new code, I post as a new thread here.

The major initiative of posting a new thread is, RobAu has posted a smarter idea, and there is no implementation, and I implemented the ideas and has simple prove the ideas is correct. Post my code and simple prove here for advice.

The problem,

I'm working on a problem to find wholly repeated shortest substring of a given string, and if no match, return the whole original string.

Input and output example

catcatcat => cat
catcatcatdog=>catcatcatdog
aaaaaa = > a


Major idea of the algorithm,

Try to match the first shortest repetitive candidate as the first character of original string, if there is no match, treat the whole non-matched string as next candidate.

I have a simple prove why if there is no match, treat the whole non-matched string as next candidate is correct,

1. Let us say, previous candidate length is N and is not satisfied during current comparison, previous matched length is N*k (previous candidate matched for k times)
2. Suppose and there could be another satisfied candidate, whose length is N+x (1<x<N) and this candidate can match p times for previous matched string. Then, N*k = (N+x)*p, in other words N*k/(N+x) = p, since N/(N+x) is not integer, but k and p are both integer, it could not be satisfied. (At the same time, we know if N length string does not match, 2N, 3N, etc. does not match, it is why I choose x as as value between 1 and N in previous analysis.)
3. So, we have to treat the whole mis-matched string as next whole repetitive string candidate.

My code

def check_shortest(original_string):
current_candidate = original_string[0]
j = 0
for i in range(len(original_string)):
if original_string[i] == current_candidate[j]:
j+=1
if j == len(current_candidate):
j = 0
else:
current_candidate= original_string[:i+1]

return current_candidate if j == 0 else original_string

if __name__ == "__main__":
print check_shortest('catcatcat') #cat
print check_shortest('catcatcatdog') #catcatcatdog
print check_shortest('aaaaaa') #a
print check_shortest('aba')  # aba

• (For python 2, avoid range habitually.) There are bugs when the string is short ('aba', check j on return) or the pattern ends as it starts ('abaaba') - not confident that this can be reconciled (aⁿba²ⁿabaⁿa - I think a repeated character at the start is the special case. Keep the length of that, new candidate shorter by that (and j reset accordingly) if j no larger at mismatch?)(failed proving RobAu's answer). – greybeard Oct 23 '16 at 7:03
• a² = aa, a³ = aaa, …: the ⁿ in (expression)ⁿ means repeat expression n times. – greybeard Oct 23 '16 at 8:33
• (Lin Ma's edit to revision 2 didn't touch anything addressed in Dair's answer.) – greybeard Oct 23 '16 at 8:36
• @greybeard good find. let me think a bit on this – RobAu Oct 23 '16 at 17:22
• Did you try 'abaaba'? Result? (Did you try ""?) – greybeard Oct 23 '16 at 20:43

You currently write:

for i in range(len(original_string)):


Consider using enumerate:

for i, char in enumerate(original_string):
if char == current_candidate[j]:


enumerate allows you to reference the current object in a nice manner, while also giving you the index that the item belongs to.

• Thanks Dair for the advice, for the correctness of the algorithm (I find the right shorest repetitive sub-string for the whole string), do you think it is correct? – Lin Ma Oct 23 '16 at 5:23
• @LinMa: I'm not sure at the moment, I posted this answer on the assumption that the algorithm is correct. – Dair Oct 23 '16 at 5:24
• @greybeard: You don't need it, but is common not to index variables explicitly unless you have to in Python. Also, i can still be used. – Dair Oct 23 '16 at 6:29
• @LinMa If your code is broken, it would be off-topic here... – Graipher Oct 23 '16 at 10:04
• (@Graipher If the code didn't appear to work when posted, it would have been off-topic. I found the algorithm a bitch to reason about, even to test.) – greybeard Oct 23 '16 at 12:17
• Use documentation strings
• comment
• use telling, but succinct names
• try to keep things simple
• (test "first": When putting considerable effort into implementing a procedure, have a test procedure in place to sustain confidence that it does solve the problem)

NOT quite successful attempt to fix RobAu/Lin Ma's approach, and no longer simple:

# Find "period" of a string:
# prefixes, grown as needed and warranted become candidates
def shortestCover(original):
"""return the shortest substring of the argument
that equals it when repeated an integral number of times.
BROKEN(incomplete): fails for 'ababccabababccabababccab'
(repetitions of more than just one char
at start _and_ end at special positions)
"""
print "shortestCover BROKEN: fails for 'ababccabababccabababccab'"
# length of prefix of original that might cover it if repeated
candidate = i = 1
oLen = len(original) # define halfLen?
#  print original, oLen
prefix = 0
while (i < oLen):
#  print i, candidate, prefix
# no need for modulus:
# the immediately preceding occurrence of
#  the candidate pattern is as good as the first
if original[i] == original[i - candidate]:
i += 1
else:
if oLen // 2 < i: return original
# part or all of prefix has unsuccessfully been assumed
#  to be the start of the next occurrence:
# candidate may need to be as far back from i as prefix,
#  but must grow
# (without re-scanning that part,
#  this does _not_ raise WC run-time to O(n^3/2) )
if (i <= candidate+prefix):
candidate = max(candidate, i-prefix)+1
# comparisons would be redundant upto&including i
while (0 != oLen % candidate
and candidate <= i):
candidate += 1
else:
candidate = i + 1
# if prefix isn't set yet,
#  original starts with i occurrences of its 1st char
if prefix == 0:
prefix = i
# allow divisors of original length as candidates, only
while (0 != oLen % candidate):
candidate += 1
if oLen // 2 < candidate: return original
# this may skip characters that never get nor need to be
#  "on the right side of a comparison for equality"
i = candidate if i < candidate else i+1;

return original[:candidate]

import re
if __name__ == "__main__":
for o in (#'',
'abababab', 'aaaaaa', # not a prime length
'ababa', 'abaaba', 'abaaaba',
'aabaaba', 'aabaaaba', 'aabaaaaba',
'aaaaccaaaaaaccaaaaaaccaa',
'ababbbabababbbabababbbab',
'ababbbababbbababbbababbb',
'ababccabababccabababccab'):
print re.match(r'^(.+?)\1*\$', o).group(1)
print shortestCover(o)

• Hi greybeard, tried your code works and could you explain what is the logical meaning of candidate = i-prefix and logical meaning of prefix itself? – Lin Ma Oct 23 '16 at 21:33
• Thanks greybeard, I will study and debug more, would you mind to add 2-3 sentence of your algorithm in brief? It helps others (e.g. for Mr. RobAu. :)) to read better. – Lin Ma Oct 23 '16 at 22:04
• Find an issue in your code (not a bug, but a bit weird), you assign prefix = i only once, and prefix is always 1, is that what you desired? – Lin Ma Oct 23 '16 at 22:26
• Delete done. :)) – Lin Ma Oct 23 '16 at 22:27
• Hi greybeard, have a chance to study your code logic in more details, your logic works in this way (please correct me if I am not correct understanding), if there is a mis-match at position i, you will set new candidate to be original_string[0:i], but you never compare if set candidate to be original_string[0:i] works for current position i or not (in next iteration, you will increase i, and do you need to compare if original_string[0:i] is good for i?). In RobAu's algorithm, if there is a mis-match at position i, he will set new candidate to be original_string[0:i+1] – Lin Ma Oct 24 '16 at 0:58