Naive String Matching Algorithm

Video Credits:
Pulkit Leekha

[laurenbouhnik]

"string matching is just.. a matching of the strings" :D

[wakideuxavila]

"love you guys" at the last part hahaha

[GuillermoRobles]

It's pretty cool that you can find a pattern that simply.

[RamytRamyt]

Great vid, but the shift starts at 0, not 1.

[YOGESH]

The Text Array index starts from 0 thus you don't have to start the "s" counter as s + 1.
BTW lecture was good.

[DevAthiest]

That was good and intuitive. Great video.

[sammymorini]

your S, is wrong... it should be S=0 at the first step, since there was no shifts as it's still at the initial position. step 2, is when you shifted once, hence S=1 and so on... until you reach S=n-m.

for complexity, there are essentially 2 nested loops, first one being the obvious for loop going from 0 -> n-m, the second one is at line 4, where it essentially loops though the pattern of size m, matching it with characters in T. thus,
total complexity is O((n-m+1)*m)

[AvengersTrex]

At the beginning we don't shift (s=0) . If s=1 at the beginning then we start at T[2] to search for the pattern, and that's an error my friend !!

[P]

great video it is easy to understand great work keep it up

[prashantkaushal]

here patter occurs at with 4 shift.You got the meaning of shift wrong brother.shift is not the index of the array.

[shubhamgujare]

nice and crisp !
can you explain me what does s+m signifies in algo ?

[AmeyaWalawalkar]

Thanks man !!
the slides ma prof gave were pathetic!!
 

[muhammednuhman]

s=4 if s starts from 0, right ?
And, can there be more than one 'shift' in a text (i.e.. multiple occurrences of the pattern in the string)

[alrasheed]

Great!! nice one and easy to understand...
thanks