Python 3.4.4 (v3.4.4:737efcadf5a6, Dec 20 2015, 20:20:57) [MSC v.1600 64 bit (AMD64)] on win32 Type "copyright", "credits" or "license()" for more information. >>> === RESTART: C:\Users\user\Dropbox\Ph.D\Teaching\IntroCS\rec9\a09_hash.py === #Check naive solution >>> repeat_naive("hello", 1) True >>> repeat_naive("hello", 2) False >>> repeat_naive("hello"*10, 2) True >>> repeat_naive("hello"*10, 10) True >>> repeat_naive("hello"*10, 60) False #Generate some random strings >>> gen_str(10) 'ggmxtlcnki' >>> gen_str(10000) 'vmwdrikcvkjvasakpfekwmyhhnnewhjbluivmayamkcqsaljdpsqxthrwggfwshxeefpmbgwiwilluwbujhnsrhykohtijxjiihzdyuacyqtwffslkqrymuszdejwtvarnbwlpfqdytwuvzuwvqoxanngrawjklshmvtymkyjcbbzwyfuhmcrtabfodwaghrwyhqqwqrvqjgilsxgfqtrcwncnoozwposhewcgopqivqqirdhfxztffxsjskftrnvjlhsinkvmclssobmhhpmugpmmlpgcqqwwwhvxmfauswvenovuuortbvnrlgbizqgrysuxcxcluacomhujdxwnujplppcxvnbvueyorelafbanceacaddivqdkkzuyzrsgzanbwshubhniizytlbsjqlocgnzrigpsodtntddxscoqsiagiqmyzqcgtdlfdjbgahsdzuqhmdbnxhekljhhgllwpnyqvjdtvgqerjrfgaydbzvcmhqdmdcturvwilbziiwrmvtnagglwvrfigmmtouctnpvdtvtcdjlpihjyalvevgqwyueljfpyiyoszbitnwtmpczvlbfkckvgdbvqxzvwrevdehdpmroiswrdsyrwmravzffqfuoctrjjpfvzacffmqtqfaokrosclztysygoytdywcalyzppobpquhatszjwezvjxkjturogrxlbebsulkpscqxnuoeestbcugvymxtqkstaaulqtvvkonwfnhkmhvuyczveeqhmhqbqvlfbhztypvmirrzohwsrhcoiqxynmmzdemrcdgyfvodmffucwfprforkbjxfcxehrpbdjmgvqylnjinocefudhgspdknlcfejzhtizeholdyzxgclrfwvfhqgmhwebkdfffstpiyyyqiqsvtdjrfneoccwbqmilignbkhdodkfeklnovlgccwiplbgtkngcnsrfrbfizowpofvyooynrqcxlcsctkwupqqlgyvefdnarwzipogwadlebckzrlqxpwlywhoyadpxqsamlxtfqavbjxjactivhfibwwpvhjnwwxutkeqpcgrfphdihtyyntlrmhzkpznpiaziafejgyeyvfufdwaetaxvtokmrbdrjrhilluxzjzkoxagxxuhutknldikplqthgzpexnhymstmhtxgkjwkiwvfcfehncrydbyvbzyjbkwvoqnicrbcrtvnbeypafuelzewrhgflugackchmxjwvegvikptdiioyjkrjasqngwhakungnkvqcekfhasizxptjeabucrexnjbppielhlalfviddwqtrlagbwuaukhuxhcowyfjiwxuofmxjzxtesgymntlxurtebbqybhssvtfisrsphunianyidkmvwtbakpvzrivjupkhqidbzqmqwarujhygbsalyfdpdzbhdhkszubbmqsfmwrtaslkzudaisiyxegwoaqtxycobcbzjolysewxcajwebacylkcsqddxrsjolwntjokxthvarsesrnikptsppifzzzhfywklggqdexkewnrsvyglshdwjzohkduaqulrgsdnfpxgugsbffcgvvxzlorlrnwtcwaylllolsknunzdemaishnooqqsijpisbhqtdizptuorddojikuufdinnaidxjvximoolwlbbqnkwkxrgxpdbwqsuqlkhepkpopymwhykyyqdtsjntjcxxkunlvtlmeglmbbffpjbhfnmrsjtzdhqvmzirjyhzczjucmjfjhdppvfaztrulypyrocdvlsiagafxiobfhyonakszfbwwbyfpzuwzqcoqoubogshzqfqchcizyszabkiqjxscqelxiiifvskyyvlrpjsrlvjhagklofddczafxsuujovzottaofevdyccepwdwuiwwwurwmrkjiphltjtaswpcvqbatmemavhrmyggqmbfvyvtjizumbvfkxrowaayjhehtqvbhbkbixoxmcapnnouqvvfaoklgouvquneyhoyziamzlefoczvnrasmemhrxerjkgfgyjjqietuhcwaikpbrskiqpwuskptmtvgnuuuxaoekytsrakcnqlltwpopowdoqdasfzygcotrfrqagorurumyncduuztxyowdntgulsvpiliryadlqhvpuexhfpjigkojobydufaydfxobcspsalpackkcilxqcefxhdfarhrzexctcuguoqmokdzygtopvrvqgjeyejqdgscxsrshlsbrwtppjighhdrkakjelmbjdhonuhhqsmyhzzduzliubfsptdxkhnaqjzvgjikzzjrenkdngrhswmyppufxktjcllfqotucmmrlgojcbcvswpppjcjkhzfeiunmkjynjrruqtwppmvvapbqqvwvvqnfxdnsjpcnatppxnkwobgaqxchvwrtygnnfzljcncujtdpasavpcbniahtaqoznpbccidnifsrmytlxyzohcbljbjmuginwcwkdyvxaaehwxfhvonqnvikekcosgagqtqriemtgzfznecdpczxvdrfajloclhhddsmfhfvxpnqsapkcklerdwsidajfpcicetqigjxyreqycvsibddjzqnczxxtjlabbccfloghhjazggvakxosrwxsfwryoqithgkluqxyxgivnzstntumhvgxsgilqwilvltopetojzyrpltgszypijfdkqbcgdvepngcelfvisxzaauirozcsiairwxjzdnhrjfaybrqnsdfrngueebarwinqwfjpjfvdismrpxnabxgadzjzsvsutyleabucblqkezemvvivjudzjipztsvizdpvxlvvadbnqkilgcbxnmdmbxtyrwbqeepekzpwnpnqtmusbhrtsoqqbxscfftmhzgozdfprkxeolycgqxxflmagndrbxbkwreshyrnjpzcistjfgokqjvozleirlncqvlzttytubrtnbigtsduwxazehfkzmglzciapbykonkokopiqhhngaegwuyljivpcplutewqnddewgfrfhlfjnsaojzxwmwvfofckycwofbwqwjbkvzseuvymrngbouencoquhbpgklchsrhejimpzfsjvfywgpdrmxvszqzffiovtjjhotpliozikiypmkphiipjminjjariiozqhuwcslusggawhbmuyhnxctpfjapcvtjtzhlxlgfnuoavhqickyxnvyltuufxlqgsllvbkgtzgoxowxcmwlbxnnjlydfglysjgdlbnwajnvfidodcewleuioskyunhvjadklbvyovjojeojecxnuadihhemozbgsipvdwubpfaaucmxskgijojyflhbqulpferllysxvmpqktnnollzroxcgtetpezprnvdskoxzgsbfoeyzpckwmhpunbcmfaemnavylrcbddawjdaatxiawyjnthvpcpijgbtjywupjjirgqwrtipzokkghooahmlknuxjthkjuspytrwzhpbhpejoczgtqdefmxuugkqbplaigmimopculybbhnnvmosellsxsyaqdanpuagpbjynawsyyaujihpakkpoaolxhoiqigtbrdzjcdrssjiazhibomubvsqqurckxymdqvfchohnifpvslgsmkopbdgvspormjdidmvjcsmscuihfvpxvgaxjflrasrbzfaylsclpsysdmgxisdcpbvdeciwckayouftlhwuyedmlphtzkkxwvccqtiiiohbzfrtnvdgkjhiqloeulrjwdbqzurktzyhhiayagqkaiictibibziltntvblgzdmgilbwfirxabfrjdiylcjmxwfnaonixusulemrhykrshmcbniwabyxmacqnrkscnlqfzyuxxtuiylkwpgohmhpjcigqqerhfpxanofwsrygjoqiskojwmrvtrrnqdizlxsnqaqhlhtghqvrqwjwrnbwfbzxhfbidaguydyhvwjumnkijnscauwcdzhdsslltnfwobmppvgwklqutyovabigvxyxfafdjzmsunsdfvezejwzywzshzadcsxidpgzvsfodxvsopjfrzawcgexxdfjtzccklbzwcmejvwrwpjslvihmhqwlpzclmlhuplevslnqvknjjwzhjxbuozfikiqaxxuusilcujvzyrbsdstrbspygugxudqblzfpwlpthapwmjyqlfxpiukuqlmipkpzrfejypqzemkaoojijfgbpwtonzoisrhlsqgciukwphaebgeimxphjarrafctuivwlybmzaghkdzefhwobevndwyrvjticaauitcbfaqsvvrisekgsmexgbhjjebbexgjdonloztzlkypfyhmahzocvdroqyflplypeuojflepmwrxmrgcuxinitxbjhwuaerrhnucacjtpeeiqknkqxrlbfadljjmbroojayaemwdaddocyvjdnrsgtpejszkcooaikidyyyeqwzxbqieugnscbcjimuuouoawfvjywfbagadhptnsaasfonmsfxdghvkbtncradsriyeqqurhtuqzyyjnakrnbptqsosrgjgxyklyjmbtajzlyscwsetjgevixoclusqdqtqpkpqbsbreowzmxctolmzggqssghpivrlrmrpxgeovjciaqjmqihnddhczwkdlieqylxesngogsqgcumlsnpcfdzumnchozkwemlhatvwvgeergkqgkunvnymsbzbnziivwchnsdkqunrqknzkqvqqtgqyxdbebklgqwewzpsnoocifaowznistkhsmfvkdrexpdvwbcbimntnghnfmeyyxfkkjfrygdctjslvfonwrunmvxidjndmruqmqsmaepmfuvivyyaiqmgxvwofbvwbxakdpskagoevaxjmidepqpexssjqcvxelqwglfnprktyjttxabewhychbkxwzkwcwqmkdgwokvryicxnzbhigsdtweuzwtibqkpzojwmwkeekufydtcmyrjkknhgjxxlhkjssmtrngeaectqteoybvsadhniehsxmgolosyplinxnxtgmvkpprbstkazjwumdhwmkkgbsxgbxpollgjxncwnkuiuxagthppfpqevzhdpkilelyjvfdambpsumoyfxhnksjblgeoveyptkkvehevknieliitupunuvqlrppkktckpgddkhibmfxeamkpfeyjedwsohjqtbwrhllxgvkjiqbwshmziaxxpluggnpwhjaanycaixxbxevvlzyrfrbajejaevrvqttdfzjjyhtxtdphsfbsxdzzmbnfpiplykxhpyykbbuyrnhinyzcvxthqwymcwiydiabkwisskoeowkouosuijdijwemiaittjavctekfhvpsvnanhjdcvpdazkitmvtkgabxtgwlaiugvrlszrjkzrzxaoiaubzdetvwluhnchuhvkblwxfzumwbjevtjgfmlwqisoezqwbjpzxlgsrbwgvdmfwilwkrglxtbjzxetmjrorhlofqitqdknyjlraxxnoywdngrxcatqaflgybqsyzwkpyyxogmcliknwdlotsrooszzbbaeqqgxxgqkopoawelumutaenpzzhhaspejylihyeicmprmcrrqbibeetcwexjdipadxowzjkdognjzxomxshzxierkqgzmahqgcyrniufxelymevxunporpynolbmfbttrsetwafwasjcvjjpxmrcpwqumbchxlrysssaazpcslyvqxtqqqpueqgndmabrpmvijxaoffxaynwxpjonswidfeehypsyjjjstuplmawpyzunkeufrpnxmqpgyvyqunxvcfgipxnovsghdxkqxaynuraqtoydxgdwsafaekmslyecatnrurjltvrcfghbcjccfptbcgmphbvwjmnwnixchuykbzjzpuaptyvxesvxppchmbvcqwfqgbwgckeftlaezmorrchffieiolvvlkzehlaalfgutzpxqecndjpkawfzotnzqpqjylyzqmsfknogmzeruhvqbclruyoxspjcmdpdkvxphgthbgftwonvezffovltbwqjtgdxgcnovlafxayvqpgeqovdzobxmlnqsdrzuijrehvqdjcnvdoblohjsfbqcnfbmeewrpqtgpbuwszlafobxgbfjmnrmmfcvcndeoavbyefpqrfnklfjqdlcxrsutivsjnoszuzxwmsvjogqztxsrxcmluqisrvtlwgqayouqpiyrghbujyghdjbmbzggqniqwuwlknexravojinemvgsnfzvmabzrqsqaayukghwxxtfjjbjrgmozunsmttbtlvvivslojlesmrkuvftpqplfczylbrxsjzwmnzkenwgtxqsbnlonznaycwxsjqyrlmahhscfktkxukfcadxwvrqqvvmwnylugucckchgjjxzxliwjvayfjrvzzmxermimlskmvjauainhidcjhoycfwcrhsqrmaiuvevzqtbxfhiqgohuwbvfixwzkqhfdafvxpymojbswchjtrqfnbuwwsjsybclanoavucbhjsnzezobazilxzroygrnfplzbcptbrfqwtgdtqilcguyuendtqrrkliiggpfznlmakyhdlyskoctjtepfqobfcmvggvgkedbjjgqcqcmautteampfbowkyvkeiortmxvqngymrnjkpsjdrwqupmgnpwqxhlhybvqptqhfnkwdvxitqwabxfxuiuugscfqalxfarjmpurepaapddehubgquiuftyotwebugvuxboybfbrehvrulwrcboeourofmeinqdmyvcxrtsznreinnsfnktbyvfwevgcqwzhjustakybmymjitruavewrgfcmyzacohucfllpeouivdtiolwnkwhlqyyzwxwzjymyezawjxyaksyyrfsjxtpgoyndxvwvkhesiailezwyxgfcnyeurzprxfalihyndywhowzealcrgllovevzlhszjduyyffdgnwlxmmnobzgkpkfdbjfewittyvnplgnjdrreaojefnpehbymzponpilefjxqqjomjbjtqdcalfiqyilcvpvochdwjyhrsppbyldvahnkzpmlrunxtusmjdeglbydpdesvunhfsanfhseiatxwagrbiicqtaobziwqwtxxoipnqcfpdquovnmwhpaifoyioxrsxwilgpicpgdosxkullqmnqefwnmtjunqvsrrfizyaeysngocmlnndctnjngeqsbydimsjmqrtnqbojxbwvqbtzjsxsyvmwdilpopuywnhzcaitqpyplnialbxhzmyimkibbqzlnkbqphuexfdmxwhttsmtsgtptddfxbarpxgnhlfwfuosfalkrilflqkxwrqnepcvmawadxvjsrdoceepajdemmzlrenifauuriieaibdkdcztwgbmzpphxxjenthrtqusmlkfdojozrqbshnfxvpfffgbfizmpapcrvtmphynwrbdhkoplxvggpmafkndovmitjsojvbubpayrplpxxhrlggoxnshbnxgdyykdduvfuhgbojgybzgufazxypddbbuykbvqruiifshcewlxrkxiihocylttqnwbotgkerdinwfbrrqkiqxalmogldqcasyttaiovyuclivozbjcasfrhoxdxxnhnhemxbaewfwukxctxahihjktwzlixzhjdpbalsaofwfaogbfgyutvsgdlhalywgdxirxvrujnblpinftkrhgmszddmhtycieevpbxapbuvukudvbdazxuecslenqpieeyoiiiewehegqibxcxcmbwyqzcfbipkcewzmjtmhxuolyxcynsimfsudumwszmdkoxukypejefofkagambljonyvkdhhjfhqtxdvhaspixebyslomzcrgrfcummdnhedkiixbxgxojwxscivutojgxzommwngazvfjpoklwvnffgwelfdgzctuhfroivvbqxojdfnkkwmirlszefevldyeppohqinqdushlxoymephzjbagshckblzkivjosiedmppemoygrrattymqgwworcbpplnyvcigqhshsbsvqmdkxzcjytkyjpqrnglesbappzzkmqckipokkzmuzkxewylefhmurabesappphuhvkrhdfjtlknokgipxoqffhdseenuxzxblkjmevpfyytmekppohnzsfpwditckoricsnopwcwaphbrvfupxiljiaovcmpromexkebanujdhzgrsxypuixbfdqkwqspyorufcdlxvahfzhwgymuaqqvtoeolojvypjvcvuoiidufmddjbuhfgrrspbikmqvxnzpdnmvxjmhynmtpixkkkoolricacccnusngkqvcevolwhqgomprtdgmkgukiuwulgcoryoqbvmfhodmyhzaorssrboyjhokrohktphyjzrsrlinjjwdyierhbbmatooxhtfghviuhyvhtdubaibeapyppjkroztjxmjawmeivkzdovohfjrxyfjfzqzybzufpsxiusxrysgzlzkmecdxzidlqawogefqxbeblntsuvlleielhdlmcspdugcoulqxfbjxjieywphpjlvypgybazqkbsphtndxcugzbnkoxbepfrmbvtqgnmwnukuypdnhmwycgoezuqqhikaaftblwelgzqxqhbxandbqvhvcgjeotwpdntqyiiseuaagvgrxiwlnkmlwcvjcnenvtadoxsfcervdamlrtlpwhaoxhdaylpzldchyrwztroslyvehojoxtbmverflpacrsyffuwddzswhehqjyuzrgprofxwpfubhktfufrmozlunwvnrjxiaouyzfhwwqebqaxseifssumuwynoxudmmskvfbifofzewenmfqvkclxvweoeilqusqvqdjlrylayqtnyjibidwhfjctcobpibvppssruahathzkskzcfavrvanxkuoxawifiwneowodvotwqyzofqrkcdofistklnzijytpqntgnvwjprygfsvggygyhstsmbtgkktbeanzivhcmgulpznziaqdcemmjytufbepjtemihdaurwvdnyoukvnudwuxgakfuyaanbwcqtkmmgbhzygicthxcvwzdsioonhvjyrkgqgpeuqoumxfllmtptvilmqpgselumnlsbsbrzfdtbnxowymtwxffkflnbuizqfovnlulnjhnukwmjyabecxeaufqkedkntfifbzokpcblnsxipqmckjtmwplegixxhmdpkdwdxhntvofmunyprmikcakrzlkzrjbzelwrimauqyagpiafmwestcyobpgpvoncrdufgdxvfopdemjcmljboxzfqkepjhjzowmfyusewuhfsagutxnzpqsrspapqaderxoufxtolsrtxilqrhbybpkfbenhbriafjibvmlggarlwksbtzszubanoxmewxjmcktifnmopwvaorqdrqflbycufkxntkrjoqwdvqdwdijkqtfnzullobcimrdvqgvlfhattkxtvuttfnmsrbnlkbmwlwvqyezngprvshysnfiqrvbbwjjcyczfzihhzfmbcssnfgjnuxbxodpyqaxkxodotgrydifwnvplgqduhhgyjvvyiuoyvxmnyqoaqoijvxorattdiwqwwzxlxwdrdarlrnxjrssehohckfxbguuoafqryigfanivbixzxtahrqmfgvxxdoemhxyswhewdkmsvhdazltfbpijfuyjzvbjctqubuhktnhuusjtrkwitpotmofluqqasifcsphgswqfhpvmoehueycutswswmbncgdakpplxdqxowgckojffnkqkmgmrsfektjplujbrpfrgfomrrscgihmxqoqeysdcxrnpsosqhshsncm' >>> >>> repeat_naive(gen_str(1000), 4) False >>> repeat_hash1(gen_str(100), 10) False >>> repeat_naive(gen_str(10000), 10) #took too much time Traceback (most recent call last): File "", line 1, in repeat_naive(s, 10) File "C:\Users\user\Dropbox\Ph.D\Teaching\IntroCS\rec9\a09_hash.py", line 8, in repeat_naive if st[i:i+l]==st[j:j+l]: KeyboardInterrupt >>> repeat_hash1(gen_str(10000), 10) False >>> repeat_hash2(gen_str(10000), 10) False >>> === RESTART: C:\Users\user\Dropbox\Ph.D\Teaching\IntroCS\rec9\a09_hash.py === #Compare solutions str_len= 1000 repeating substring len= 10 repeat_naive 0.23019628540829204 found? False repeat_hash1 0.0018553615408817281 found? False repeat_hash2 0.0008388602711433268 found? False >>> === RESTART: C:\Users\user\Dropbox\Ph.D\Teaching\IntroCS\rec9\a09_hash.py === #This time double string length str_len= 2000 repeating substring len= 10 repeat_naive 0.8808399971735343 found? False # times 2^2 from prevoius run repeat_hash1 0.003790069394469242 found? False # times 2 from prevoius run repeat_hash2 0.0011815100195443629 found? False # times 2 from prevoius run >>> === RESTART: C:\Users\user\Dropbox\Ph.D\Teaching\IntroCS\rec9\a09_hash.py === #Hash table creation should also be considered str_len= 2000 repeating substring len= 2 repeat_naive 0.0012770414010111325 found? True repeat_hash1 0.0010603193827251611 found? True repeat_hash2 7.855679715648711e-05 found? True >>> === RESTART: C:\Users\user\Dropbox\Ph.D\Teaching\IntroCS\rec9\a09_hash.py === #Table size competition - best to choose the size similar to the number of elements str_len= 2000 repeating substring len= 2 repeat_naive 0.0015537666010447659 found? True repeat_hash1 0.0010907157313736551 found? True repeat_hash2 8.842574152287397e-05 found? True str_len= 1000 repeating substring len= 10 0.09228173546570956 found? False table size= 1 0.01564938246067521 found? False table size= 10 0.008154511351062432 found? False table size= 100 0.0072118297851846425 found? False table size= 1000 0.007506713842852453 found? False table size= 1500 0.012548165382980203 found? False table size= 10000 0.05391720113579712 found? False table size= 100000 >>>