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.
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,
- Let us say, previous candidate length is
Nand is not satisfied during current comparison, previous matched length is
N*k(previous candidate matched for
- Suppose and there could be another satisfied candidate, whose length is
1<x<N) and this candidate can match
ptimes 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
pare both integer, it could not be satisfied. (At the same time, we know if
Nlength string does not match,
3N, etc. does not match, it is why I choose
xas as value between
Nin previous analysis.)
- So, we have to treat the whole mis-matched string as next whole repetitive string candidate.
def check_shortest(original_string): current_candidate = original_string 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