Python 3.2.5 (default, May 15 2013, 23:07:10) [MSC v.1500 64 bit (AMD64)] on win32 Type "copyright", "credits" or "license()" for more information. >>> ================================ RESTART ================================ #the string matching problem: #given a text of length n and a pattern of length m #report all occurrences of pattern in text #Running Karp-Rabin algorithm for string matching >>> text = "abracadabra" >>> pattern = "abr" >>> find_matches_KR(pattern, text) [0, 7] #Comparing KR and KR_safe: # We will see a difference in running time when there are many many matches. # In this case, the safe version is affected from the length m of the pattern, while the regular KR is not. >>> text = 'a'* 100000 pattern = 'a'* 100 find_matches_KR 0.13411092181695028 find_matches_KR_safe 0.18298934075633108 pattern = 'a'* 1000 find_matches_KR 0.14608224243582113 find_matches_KR_safe 0.26817881824655354 pattern = 'a'* 10000 find_matches_KR 0.11249046731096857 find_matches_KR_safe 1.1428794168125846 # How (not) to choose r? >>> find_matches_KR("ra", "abracadabra", basis = 2**16, r=2**16) [2, 4, 6, 9] >>> find_matches_KR_safe("ra", "abracadabra", basis = 2**16, r=2**16) [2, 9] >>> find_matches_KR("humpty", "humpty dumpty", basis = 2**16, r=2**(16*5)) [0, 7] >>> fingerprint("humpty", basis = 2**16, r=2**(16*5)) 2158299737877522940025 >>> fingerprint("dumpty", basis = 2**16, r=2**(16*5)) 2158299737877522940025 >>> find_matches_KR("ra", "abracadabra", basis = 2**16, r=2) [2, 3, 4, 6, 9] >>> #We saw another variant of KR which uses a different fingerprint (fingerprint_sum) #images: >>> im = Matrix.load("guess.bitmap") >>> im Matrix too large, specify submatrix >>> im[0:3, 0:3] >>> im.display() >>> join_many(im, add(im, 50), add(im, 150)).display() >>> join_many(im, add(im, 128)).display() >>> join_many(im , what(im)).display() >>> join_many(im , shift(im, v_shift=100)).display() >>> join_many(im , shift(im, v_shift=-100)).display() >>> shift_self(im, 100).display() >>> im = Matrix.load("guess.bitmap") >>> shift_self(im, -100).display() >>>