2
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ (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). \$\endgroup\$ – greybeard Oct 23 '16 at 7:03
  • 1
    \$\begingroup\$ a² = aa, a³ = aaa, …: the in (expression)ⁿ means repeat expression n times. \$\endgroup\$ – greybeard Oct 23 '16 at 8:33
  • 1
    \$\begingroup\$ (Lin Ma's edit to revision 2 didn't touch anything addressed in Dair's answer.) \$\endgroup\$ – greybeard Oct 23 '16 at 8:36
  • 1
    \$\begingroup\$ @greybeard good find. let me think a bit on this \$\endgroup\$ – RobAu Oct 23 '16 at 17:22
  • 1
    \$\begingroup\$ Did you try 'abaaba'? Result? (Did you try ""?) \$\endgroup\$ – greybeard Oct 23 '16 at 20:43
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Lin Ma Oct 23 '16 at 5:23
  • 1
    \$\begingroup\$ @LinMa: I'm not sure at the moment, I posted this answer on the assumption that the algorithm is correct. \$\endgroup\$ – Dair Oct 23 '16 at 5:24
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Dair Oct 23 '16 at 6:29
  • 1
    \$\begingroup\$ @LinMa If your code is broken, it would be off-topic here... \$\endgroup\$ – Graipher Oct 23 '16 at 10:04
  • 1
    \$\begingroup\$ (@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.) \$\endgroup\$ – greybeard Oct 23 '16 at 12:17
1
\$\begingroup\$
  • 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)
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Lin Ma Oct 23 '16 at 21:33
  • \$\begingroup\$ 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. \$\endgroup\$ – Lin Ma Oct 23 '16 at 22:04
  • \$\begingroup\$ 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? \$\endgroup\$ – Lin Ma Oct 23 '16 at 22:26
  • \$\begingroup\$ Delete done. :)) \$\endgroup\$ – Lin Ma Oct 23 '16 at 22:27
  • \$\begingroup\$ 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] \$\endgroup\$ – Lin Ma Oct 24 '16 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.