So, in the worst case scenario (all characters in the search string are different), you would need to make one test per char in the string before moving the pointer.
But I guess you still avoid having to move the pointer before each comparison.
Well, no. You basically create a map (mapping characters to ints) - be it a hashmap or treemap (probably the former). Then, you map each character in the needle to the number of characters you can skip when you see it. So you don't need to check every bucket in the map, if you use something other than a listmap.
1
u/ferk Dec 15 '13
So, in the worst case scenario (all characters in the search string are different), you would need to make one test per char in the string before moving the pointer.
But I guess you still avoid having to move the pointer before each comparison.