Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question
this is O(n), but incorrect (as @Poik pointed out). There are no O(n) algorithms for string matching, maybe O(n+m), using Rabin-Karp or Knuth-Morris-Pratt (n=length of string, m=length of string to match). Look them up. – Gabi Purcaru Apr 4 at 18:20
1  
@Gabi Purcaru: if you need to check multiple substrings in the same string then there are better than O(n+m) algorithms if you preprocess the string first e.g., a suffix array + LCP can give you O(m + log n) and suffix trees can give you O(m) substring search. – J.F. Sebastian Apr 6 at 15:12

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
Hey Pcalcao, thanks for that answer. Actually, I'm looking for any unit test which might fail for this program, but, couldn't figure any. So, can you help in testing whre this code will break (apart from the corner cases) – GodMan Apr 4 at 17:09
I don't see any cases from reading the code, that probably means that it's working out alright. – pcalcao Apr 4 at 17:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.