while matching a string and pattern using brute force we are checking substring of length pattern at each index but if we check the substring starting from those indexes where we got the inequality with pattern then wont the time complexity decreases from o(m*n) to o(n)
for example in a string ababcabdabab and pattern abd
when we compare subsstrind from i=0 to i=2 we get inequality at i=2 then we compare the next substring from i=1 but cant we check substring from i=2 only as previous one wont match
String matching brute force
This trick wont work everytime. For example take strings : babbbb and matching pattern to be abb. i =0 to i=2 doesn’t match but i=1 to i=3 matches.
Hope it Helps.