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: 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.
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\$