### Mr.Awesome's blog

By Mr.Awesome, history, 9 months ago,

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.

• +4

 » 9 months ago, # |   +9 I guess it's a standard application of Suffix Trees. Build a suffix tree for S\$b# and then query for the LCS in O(|S|+|b|) for each query. And that should be fast enough, given the constraints.Read more about it here
 » 9 months ago, # |   +5 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.
•  » » 9 months ago, # ^ |   +5 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 ? for(int i = 0; i < S.length(); i++) { string tmp = ""; for(int j = i; j < min(S.length(), i + 100); j++) { tmp += s[j]; hash_and_add_to_vector(tmp); } } 
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +5 Spoilerconst int N = 1e5 + 5; vector v[N]; char s[N]; // step 1) First precalculate hash of string s; // step 2) Storing hash of every string of size atmost 100 // almost 1e7 operations here for (int i = 1; i <= 1e5; ++i) { // consider 1-based indexing for (int j = i; j > 0 && j >= i - 100; --j) { int size = i - j + 1; // hash (j,i) is a function which gives hash of substring s[j..i] which is O(1) v[size].push_back(hash(j,i)); } } // q * k * k // a string of size k will have almost k^2 substring for (int i = 1; i <= q; ++i) { cin >> curr_string; //step 1) Compute it's hash //step 2) for (int j = 0; j < curr_string.size(); ++j) { for (int k = j; k < curr_string.size(); ++k) { int cur_size = k - j + 1; int has = hash(j,k); if (has is present in v[cur_size]) { // Answer is found } } } } 
•  » » » » 9 months ago, # ^ |   0 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)?
•  » » » » » 9 months ago, # ^ |   0 You can refer this.
•  » » » » » » 9 months ago, # ^ |   0 Thanks :)
 » 9 months ago, # |   +7 Could you post the link of the problem?
•  » » 9 months ago, # ^ |   0 Unfortunately this is was an interview question problem.