Feb 2, 2009

Lets say you have 1 string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the big str

Lets say you have 1 string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the big string ?
Hash the all substrings of long string where the length is L into the hash table, use M small strings to look up the hash table to get the occurrence of each small string. O(NL)+O(M)
Or suffix tree.

No comments:

Post a Comment