since you have M small strings using KMP or RabinKarp will take time O(mn)
but with suffix tree you can do it in O(n+m)
read these and you'll be able to construct one:
http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm
--
You receiv
@awesomeandroid
how you will use KMP in ths case, can you plz explain ?
Mohit
On Sun, Dec 12, 2010 at 8:01 PM, awesomeandroid
wrote:
> KMP and RabinKarp
>
> On Dec 12, 7:07 pm, Prims wrote:
> > Given that you have one string of length N and M small strings of
> > length L . How do
KMP and RabinKarp
On Dec 12, 7:07 pm, Prims wrote:
> Given that you have one string of length N and M small strings of
> length L . How do you efficiently find the occurrence of each small
> string in the larger one
>
> I heard the best solution for this problem is to use generalized
> su