Possible Bugs in substring program

Question

I have written a small snippet to validate a substring in a string in O(n). I have tested the code using some combinations. I require your help to let me know if there are any bugs in my code with respect to any other cases that I might have missed out:-

class StringClass( object ):
    def __init__( self, s ):
        self._s = s
    def __contains__( self, s ):
        ind = 0
        for ch in self._s:
            if ind < len( s ) and ch == s[ind]:
                ind += 1
            elif ind >= len( s ):
                return True
            elif ch == s[0]:
                ind = 1
            elif ch != s[ind]:
                ind = 0

        if ind >= len( s ):
            return True

if __name__ == '__main__':
    s = StringClass( 'I llove bangaolove' )
    print 'love' in s

PS: Here, Instead of trying to find the string 'love' in 'I llove bangalove', I'm using the other method: i.e. to find if the string 'I llove bangalove' contains 'love'.

Please let me know if there are any corrections to be made here.

Answer 1

One case that you missed is replication in the search string.

>>> '1213' in StringClass('121213')
False
>>> '1213' in '121213'
True

This is because your class is already past the second one before it sees a difference and has to start completely over.

Asides from that, the empty string and None cases are problems, as is mentioned in other answers.

Answer 2

Your implementation seems ok, although I would test some corner cases before starting the iteration, ask yourself:

What should be done in the case s is None? or s == ''? (Both can be handled in python simply by if s:.

Besides that, your implementation seems correct, implement some unit tests to cover the corners cases and the expected results.

About the complexity, it's linear in the length of the string you created the object with.