Here's a problem I crossed lately:
You have a large String S, and q queries, each query consist of a small string b.
The answer of each query is to find the length of the longest common substring between S and b. ( |S| <= 10^5, |b| <= 100, q <= 100 )
My dp solution to find the length of the largest LCS is O(n*m) per query, but it doesn't seem to pass!
I think will need to do some pre-prcessing of S before starting quering, but I can't find a solution.
Any hint or idea will be appreciated.
I guess it's a standard application of Suffix Trees. Build a suffix tree for
S$b#
and then query for the LCS inO(|S|+|b|)
for each query. And that should be fast enough, given the constraints.Read more about it here
You can use hashing. Let the original string be s.
First precompute and store hash (in a 2d vector let's say) for every substring of (size from $$$1$$$ to $$$100$$$) string s. Now for every query hash the current string, and look any of it's substring hash is present in precomputed vector of it's size.
Thanks for your reply, but isn't the complexity of this is 100 * |S| * (complexity of hashing each substring) ? Is this a right code for your solution ?
This a great solution ( more thinking and less data structure ), however I still doesn't know how to compute the hash of a substring of S in O(1)?
You can refer this.
Thanks :)
Could you post the link of the problem?
Unfortunately this is was an interview question problem.