What I suggested is optimal and doesn't require you to reverse the strings. It's not hard to see that it takes O(n + m) which cannot be improved on.
Additionally it works for any other search algorithm than KMP. On 7 April 2014 20:41, Dan <[email protected]> wrote: > Depends on what language you are using??? > > Fortran has this capability built directly into it's standard Index() > routine ( ie. it does what you might call a 'backwards' search). I > imagine other languages have a similar capability. If not, and the > strings are not huge memory hogs... or if you are ok with overwriting your > original string, s1 in the process: > > Invert both strings. ie rearrange them such that the last letter of > each string becomes the first, etc., etc. > > Then use your languages normal INDEXED type of search. > > Otherwise, you'll just have to do an Indexed search repeatedly to find > the last occurrence... or... write your own special Index function. I'm > not sure what the fastest search algorithm is for that. I seem to remember > reading up on it a long time ago. It's not a brute force method if I > recall correctly. > > Dan :-) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
