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 =&gt; cat
catcatcatdog=&gt;catcatcatdog
aaaaaa = &gt; 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,


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)
Suppose and there could be another satisfied candidate, whose length is N+x (1&lt;x&lt;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.)
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
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.