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 <dant...@aol.com> 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 algogeeks+unsubscr...@googlegroups.com. > -- 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 algogeeks+unsubscr...@googlegroups.com.
