Functional implementation of classic substring problem.

substr.py

def substr(sub, match):
    '''Returns True if `sub` is a substring of `match`.
       Example: substr("abc", "abababc") # True
    '''
    def sub_helper(sub, match, fc):
        # Base case: empty string is always a substring
        if len(sub) == 0:
            return True
        # Reached end of `match`, but haven't matched all of sub.
        # Call failure continuation.
        elif len(sub) > 0 and len(match) == 0:
            return fc()
        # Prefix matches. Now try to match the rest!
        elif sub[0] == match[0]:
            return sub_helper(sub[1:], match[1:], lambda: sub_helper(sub, match[1:], fc))
        # Prefix didn't match. Try matching `sub` to the rest of `match`
        else:
            return sub_helper(sub, match[1:], fc)
    return sub_helper(sub, match, lambda:False)

if __name__=="__main__":
    assert substr("", "") == True
    assert substr("", "a") == True
    assert substr("", "aa") == True
    assert substr("a", "aa") == True
    assert substr("aa", "aa") == True
    assert substr("aa", "a") == False
    assert substr("aa", "") == False
    assert substr("aba", "aabaa") == True
    assert substr("aba", "abaa") == True
    assert substr("aba", "aba") == True
    assert substr("aa", "bbbbbbaa") == True
    assert substr("aa", "bbbbbbaab") == True
    assert substr("Bea", "Alex Beal") == True
    assert substr("Bea", "Alex Bell") == False
    assert substr("abc", "abababc") == True
    assert substr("abc", "ababab") == False
    assert substr("abc", "ababcab") == True