Created
June 20, 2015 19:42
-
-
Save cjauvin/789130e3b43252bfee1f to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import re | |
| from colorama import Back, Fore, Style | |
| def shingles(s, k): | |
| ts = set() | |
| for i in range(len(s) - k + 1): | |
| t = s[i:i+k] | |
| ts.add(t) | |
| return ts | |
| def substrings(s, t): | |
| ix = -1 | |
| xs = [] | |
| while True: | |
| ix = s.find(t, ix + 1) | |
| if ix == -1: | |
| break | |
| xs.append(ix) | |
| return xs | |
| def ranges_to_bitarray(rs, n): | |
| b = [0] * n | |
| for l, r in rs: | |
| b[l:r] = [1] * (r - l) | |
| return b | |
| # sim_range: (i, j, 0|1) | |
| def bitarray_to_sim_ranges(b): | |
| if not b: | |
| return [] | |
| rs = [] | |
| ix, i = 0, 0 | |
| for i in range(1, len(b)): | |
| if b[i] != b[i-1]: | |
| rs.append((ix, i-1, b[i-1])) | |
| ix = i | |
| rs.append((ix, i, b[i-1])) | |
| return rs | |
| def color_sim_ranges(s, srs): | |
| t = '' | |
| c = [Style.RESET_ALL, Back.YELLOW] | |
| #c = ['*RA*', '*Y*'] | |
| for sr in srs: | |
| t += c[sr[2]] + s[sr[0]:sr[1]] | |
| t += c[0] | |
| return t | |
| K = 20 | |
| a = """171451119\tWomen's Dresses | zulily We detected that your JavaScript seem to be disabled. You must have JavaScript enabled in your browser to utilize the functionality of this Web site. Become a Member Already a Member? Sign In ILS Loading... Something special every day Invite Friends, Earn Credit Basket New today Best sellers Last day Shop by category girls boys women women - plus sizes men shoes health & beauty baby & maternity toys & playtime home ready to ship Shop by size Girls infant (-m) toddler (T-T) kids (-) big kids (-) shoes toys & playtime Boys infant (-m) toddler (T-T) kids (-) big kids (-) shoes toys & playtime Women juniors women plus-size maternity & nursing shoes accessories home & décor SEARCH Welcome to zulily!Daily deals up to % off Read about us in A Casual Beauty vivid, carefree dresses | New today! shop now Dressed for the Day liven up the office | New today! shop now Maxi'd Out floor-sweeping looks | New today! shop now Be Vibrant at Work spring-ready dresses | Ends / shop now The Versatile Wardrobe day-to-night dresses | Last day! shop now Carefree-Cool to the Max with s.h.e. & london times | Last day! shop now The Breezy Bohemian free to be bright | Last day! shop now Karen & Nommo made in poland | New today! shop now Maxi Madness find a flowy favorite | Ends / shop now PURO LINO made in italy | New today! shop now Trend Wednesday in Plus-Sizes all maxed out | Ends / shop now The Free-Spirited Way a bohemian season | New today! shop now The Edit | Sol Seeker featuring parides & more | Last day! shop now Go the Long Way with season-ready pieces | Ends / shop now Ananda's Collection Plus-Size floaty, vivid designs | Last day! shop now Solo La Fe mommy & me | Ends / shop now Bump Up the Trend nursing features too | Ends / shop now Looking Sunny in Plus-Sizes for the beach & beyond | New today! shop now Soak Up the Sunshine your carefree staples | Last day! shop now zulily debut | Comptoir du Lin made in italy | Ends / shop now A Vibrant Point of View captivating prints & cuts | Last day! shop now Be a Free Spirit go for unique | Last day! shop now The Palazzo Pulse with tops to pair | New today! shop now LuvLuv with crochet & embroidery | Ends / shop now From Office to Evening key pieces for your closet | Ends / shop now A Bright Outlook in Plus-Sizes tunics & dresses that pop | New today! shop now Green Dragon & Pink Lotus boho-style outfits too | Last day! shop now THE LIST | Model's Weekend Look from sporty to feminine | New today! shop now The Block & Stripe Hype a trendy mom-to-be | Ends / shop now Premise Paris & More funky euro fashions | Ends / shop now Other zulily finds you'll love! Aerosoles with wide-width styles | Ends / shop now Dansko ergonomic comfort features | Last day! shop now swimsuitsforall make style waves | Last day! shop now SlimMe by MeMoi shaped to perfection | New today! shop now A Souvenir Tee for the Road graphics meant to be seen | Ends / shop now Coach & More bags, shades & watches | Ends / shop now Women's Dresses From parties and formal dinners to work events and casual summer afternoons, our women's dress selection features something flattering for every occasion. Discover long, knee-length and short styles in classic cuts including cocktail, sweater, evening, shirt and a-line dresses. Look for plunging necklines, empire waistlines and formfitting silhouettes that trim your limbs so you're always drawing attention to your best features. Wrap dresses, in particular, look great on every body type. Browse through a variety of materials such as classic cotton, cute denim and beautiful chiffon. Never underestimate the power of the little black dress fashion staple. Try one with playful sequin detailing or gold trim if you want something a little more unusual. Summer styles in cheerful yellow or pink are great for daytime wear, while adventurous gowns in deep purple or red are perfect for special evening events. We offer a variety of sizes including plus, petite and regular. Our selection changes every day, but always features cheap, discount prices! See more > Women's Maxis Women's High Low Dresses Lace Dresses Women's Formal Dresses Summer Dresses New Today Best Sellers Last Day Shop by Category Shop by Size Already a member? Sign In Daily deals up to % off! sign up for free and start shopping email address yes No, use what I entered: Shop Now So much cuteness just around the corner... email password your name Hello there! Create a password: password continue I'll take one of these, and one of those... email password your name You're almost in! What's your name? first name last name start shopping By signing up, you agree to zulily's Terms & Conditions and Privacy Practices. Not a member yet? Sign Up Sign In Welcome back! Sign in to continue email address forgot password? password sign in now By signing in, you agree to zulily's Terms & Conditions and Privacy Practices. About Us Investors Brands We Love Careers Terms & Conditions Privacy Policy About Us Brands we love How zulily works Careers Blog Investors Contact Us Feedback Sell with zulily FAQ JOIN US Facebook Twitter Tumblr RSS Pinterest SHOP ON THE GO Get the app! Terms & Conditions Privacy Practices Product Recall Categories © zulily zulily UK\n""" | |
| b = """171456462\tWomen\'s Dresses | zulily Already a member? Sign In Daily deals up to % off! sign up for free and start shopping email address yes No, use what I entered: Shop Now So much cuteness just around the corner... email password your name Hello there! Create a password: password continue I\'ll take one of these, and one of those... email password your name You\'re almost in! What\'s your name? first name last name start shopping By signing up, you agree to zulily\'s Terms & Conditions and Privacy Practices. Not a member yet? Sign Up Sign In Welcome back! Sign in to continue email address forgot password? password sign in now By signing in, you agree to zulily\'s Terms & Conditions and Privacy Practices. close <div class="noscript"> <div class="noscript-inner"> <p><strong>We detected that your JavaScript seem to be disabled.</strong></p> <p>You must have JavaScript enabled in your browser to utilize the functionality of this Web site.</p> </div> </div> Become a Member Already a Member? Sign In USD Loading... Something special every day Invite Friends, Earn Credit Basket New today Trending Last day Shop by category girls boys women women - plus sizes men shoes health & beauty baby & maternity toys & playtime home ready to ship Shop by size Girls infant (-m) toddler (T-T) kids (-) big kids (-) shoes toys & playtime Boys infant (-m) toddler (T-T) kids (-) big kids (-) shoes toys & playtime Women juniors women plus-size maternity & nursing shoes accessories home & décor SEARCH Welcome to zulily!Daily deals up to % off Read about us in A Casual Beauty vivid, carefree dresses | New today! shop now Dressed for the Day liven up the office | New today! shop now Maxi\'d Out floor-sweeping looks | New today! shop now Be Vibrant at Work spring-ready dresses | Ends / shop now The Versatile Wardrobe day-to-night dresses | Last day! shop now Carefree-Cool to the Max with s.h.e. & london times | Last day! shop now The Breezy Bohemian free to be bright | Last day! shop now Maxi Madness find a flowy favorite | Ends / shop now Karen & Nommo made in poland | New today! shop now PURO LINO made in italy | New today! shop now Trend Wednesday in Plus-Sizes all maxed out | Ends / shop now The Free-Spirited Way a bohemian season | New today! shop now The Edit | Sol Seeker featuring parides & more | Last day! shop now Go the Long Way with season-ready pieces | Ends / shop now Ananda\'s Collection Plus-Size floaty, vivid designs | Last day! shop now Solo La Fe mommy & me | Ends / shop now Bump Up the Trend nursing features too | Ends / shop now Looking Sunny in Plus-Sizes for the beach & beyond | New today! shop now Soak Up the Sunshine your carefree staples | Last day! shop now zulily debut | Comptoir du Lin made in italy | Ends / shop now A Vibrant Point of View captivating prints & cuts | Last day! shop now Be a Free Spirit go for unique | Last day! shop now LuvLuv with crochet & embroidery | Ends / shop now The Palazzo Pulse with tops to pair | New today! shop now From Office to Evening key pieces for your closet | Ends / shop now A Bright Outlook in Plus-Sizes tunics & dresses that pop | New today! shop now Green Dragon & Pink Lotus boho-style outfits too | Last day! shop now THE LIST | Model\'s Weekend Look from sporty to feminine | New today! shop now The Block & Stripe Hype a trendy mom-to-be | Ends / shop now Premise Paris & More funky euro fashions | Ends / shop now Other zulily finds you\'ll love! Aerosoles with wide-width styles | Ends / shop now Dansko ergonomic comfort features | Last day! shop now swimsuitsforall make style waves | Last day! shop now A Souvenir Tee for the Road graphics meant to be seen | Ends / shop now SlimMe by MeMoi shaped to perfection | New today! shop now Coach & More bags, shades & watches | Ends / shop now Find Your Signature Scent shop by note | New today! shop now Women\'s Dresses From parties and formal dinners to work events and casual summer afternoons, our women\'s dress selection features something flattering for every occasion. Discover long, knee-length and short styles in classic cuts including cocktail, sweater, evening, shirt and a-line dresses. Look for plunging necklines, empire waistlines and formfitting silhouettes that trim your limbs so you\'re always drawing attention to your best features. Wrap dresses, in particular, look great on every body type. Browse through a variety of materials such as classic cotton, cute denim and beautiful chiffon. Never underestimate the power of the little black dress fashion staple. Try one with playful sequin detailing or gold trim if you want something a little more unusual. Summer styles in cheerful yellow or pink are great for daytime wear, while adventurous gowns in deep purple or red are perfect for special evening events. We offer a variety of sizes including plus, petite and regular. Our selection changes every day, but always features cheap, discount prices! See more > Women\'s Maxis Women\'s High Low Dresses Lace Dresses Women\'s Formal Dresses Summer Dresses New Today Best Sellers Last Day Shop by Category Shop by Size About Us Investors Brands We Love Careers Terms & Conditions Privacy Policy <div style="display:inline;"> <img height="" width="" style="border-style:none;" alt="" src="https://www.googleadservices.com/pagead/conversion//?label=QLbCJDywEQnIDQQM&guid=ON&script="/> </div> About Us Brands we love How zulily works Careers Blog Investors Contact Us Feedback Sell with zulily FAQ Send a gift card Woo hoo for you, VIP! Enter the code on your VIP pass and voilà–you’ll enjoy % off your order of $ or more. activate JOIN US Facebook Twitter Tumblr RSS Pinterest SHOP ON THE GO Get the app! Terms & Conditions Privacy Practices Product Recall Categories © zulily zulily UK\n""" | |
| ta = shingles(a, K) | |
| tb = shingles(b, K) | |
| rsa = set() | |
| rsb = set() | |
| for t in ta & tb: | |
| rsa |= {(i, i + len(t)) for i in substrings(a, t)} | |
| rsb |= {(i, i + len(t)) for i in substrings(b, t)} | |
| ba = ranges_to_bitarray(rsa, len(a)) | |
| bb = ranges_to_bitarray(rsb, len(b)) | |
| print(color_sim_ranges(a, bitarray_to_sim_ranges(ba))) | |
| print(color_sim_ranges(b, bitarray_to_sim_ranges(bb))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment