• API
• FAQ
• Tools
• Archive
SHARE
TWEET Untitled a guest May 24th, 2019 79 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.

Top