0
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Apr 4, 2013 at 18:20
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – jfs
    Commented Apr 6, 2013 at 15:12

2 Answers 2

5
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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) \$\endgroup\$
    – GodMan
    Commented Apr 4, 2013 at 17:09
  • \$\begingroup\$ I don't see any cases from reading the code, that probably means that it's working out alright. \$\endgroup\$
    – pcalcao
    Commented Apr 4, 2013 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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