#!/usr/bin/env python

from itertools import izip

# Solution 1:
# Find a string in another string with a naive lookup
# Worst case runtime O(len(h))*O((len(n))
def s1(needle, haystack):
    ln, lh = len(needle), len(haystack)
    # Walk the haystack until len(needle) chars before the end.
    for i in range(lh-ln+1):
        print "%d: %s" % (i, haystack[i:])
        # At this position does the needle string occur?
        if all(needle[j] == haystack[i+j] for j in range(ln)):
            return True
    return False

# Wrapper function concatenates all the substrings in the haystack. This
# causes O(len(h)) unnecessary memory allocation.
def s1_wrap(n,h):
    return s1(n, ''.join(h))


# Solution 2:
# Similar to solution 1 excep
# A generator that takes a nested list and produces a sequence of
# indices of sublists and characters within the sublist.
def pair_range(ll, init_i=0, init_j=0):
    for i in range(init_i, len(ll)):
        if i == init_i:
            ij = init_j
        else:
            0
        for j in range(ij, len(ll[i])):
            yield (i, j)

# A generator that produces a sequence of characters from a nested
# list starting from a given position.
def iter_from(ll, (init_i, init_j)):
    for i in range(init_i, len(ll)):
        l = ll[i]
        if i == init_i:
            l = l[init_j:]
        for e in l:
            yield e

def s2(needle, haystack):
    # Generate haystack starting positions (doesn't have the length
    # optimization from above)
    for p in pair_range(haystack):
        # At this starting position does the needle string occur?
        # To find out, start a haystack iterator from this position
        h = iter_from(haystack, p)
        # Do all the needle characters match the sequence of chars
        # from the haystack iterator?
        if all(next(h, None) == n for n in needle):
            return True
    return False

search = s2
def test(n,h,e):
    a = search(n, h)
    r = "PASS" if a == e else "FAIL"

    print "%s: search(%r, %r) => %r (expected %r)" % (r, n, h, a, e)

test("cat", ["mouse", "cat", "dog"], True)
test("cat", ["ca", "cat"], True)
test("cat", ["c", "a", "t"], True)
test("cat", ["c", "g", "at", "a", "t"], False)
test("cat", ["c", "a"], False)