CODEWITHSUNDEEP
algorithm
pjain
pjain

Reputation: 1169

data structure for finding the substring from large number of strings

My problem statement is that I am given millions of strings, and I have to find one sub-string which can be present in any of those strings. e.g. given is "xyzoverflowasxs, werstackweq" etc. and I have to find a given sub string named as "stack", which should return "werstackweq". What kind of data structure we can use for solving this problem ?

I think we can use suffix tree for this , but wanted some more suggestions for this problem.

Upvotes: 0

Views: 256

Answers (1)

Ami Tavory
Ami Tavory

Reputation: 76297

I think the way to go is with a dictionary holding the actual words, and another data structure pointing to entries within this dictionary. One way to go would be with suffix trees and their variants, as mentioned in the question and the comments. I think the following is a far simpler (heuristic) alternative.

Say you choose some integer k. For each of your strings, finding the k Rabin Fingerprints of length-k within each string should be efficient and easy (any language has an implementation).

So, for a given k, you could hold two data structures:

  • A dictionary of the words, say a hash table based on collision lists

  • A dictionary mapping each fingerprint to an array of the linked-list node pointers in the first data structure.

Given a word of length k or greater, you would choose a k subword, calculate its Rabin fingerprint, find the words which contain this fingerprint, and check if they indeed contain this word.

The question is which k to use, and whether to use multiple such k. I would try this experimentally (starting with simultaneously a few small k values for, say, 1, 2, and 3, and also a couple of larger ones). The performance of this heuristic anyway depends on the distribution of your dictionary and queries.

Upvotes: 1

Related Questions