SHARE
TWEET

Untitled

a guest May 24th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python
  2.  
  3. from itertools import izip
  4.  
  5. # Solution 1:
  6. # Find a string in another string with a naive lookup
  7. # Worst case runtime O(len(h))*O((len(n))
  8. def s1(needle, haystack):
  9.     ln, lh = len(needle), len(haystack)
  10.     # Walk the haystack until len(needle) chars before the end.
  11.     for i in range(lh-ln+1):
  12.         print "%d: %s" % (i, haystack[i:])
  13.         # At this position does the needle string occur?
  14.         if all(needle[j] == haystack[i+j] for j in range(ln)):
  15.             return True
  16.     return False
  17.  
  18. # Wrapper function concatenates all the substrings in the haystack. This
  19. # causes O(len(h)) unnecessary memory allocation.
  20. def s1_wrap(n,h):
  21.     return s1(n, ''.join(h))
  22.  
  23.  
  24. # Solution 2:
  25. # Similar to solution 1 excep
  26. # A generator that takes a nested list and produces a sequence of
  27. # indices of sublists and characters within the sublist.
  28. def pair_range(ll, init_i=0, init_j=0):
  29.     for i in range(init_i, len(ll)):
  30.         if i == init_i:
  31.             ij = init_j
  32.         else:
  33.             0
  34.         for j in range(ij, len(ll[i])):
  35.             yield (i, j)
  36.  
  37. # A generator that produces a sequence of characters from a nested
  38. # list starting from a given position.
  39. def iter_from(ll, (init_i, init_j)):
  40.     for i in range(init_i, len(ll)):
  41.         l = ll[i]
  42.         if i == init_i:
  43.             l = l[init_j:]
  44.         for e in l:
  45.             yield e
  46.  
  47. def s2(needle, haystack):
  48.     # Generate haystack starting positions (doesn't have the length
  49.     # optimization from above)
  50.     for p in pair_range(haystack):
  51.         # At this starting position does the needle string occur?
  52.         # To find out, start a haystack iterator from this position
  53.         h = iter_from(haystack, p)
  54.         # Do all the needle characters match the sequence of chars
  55.         # from the haystack iterator?
  56.         if all(next(h, None) == n for n in needle):
  57.             return True
  58.     return False
  59.  
  60. search = s2
  61. def test(n,h,e):
  62.     a = search(n, h)
  63.     r = "PASS" if a == e else "FAIL"
  64.  
  65.     print "%s: search(%r, %r) => %r (expected %r)" % (r, n, h, a, e)
  66.  
  67. test("cat", ["mouse", "cat", "dog"], True)
  68. test("cat", ["ca", "cat"], True)
  69. test("cat", ["c", "a", "t"], True)
  70. test("cat", ["c", "g", "at", "a", "t"], False)
  71. test("cat", ["c", "a"], False)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top