Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Find the length of the longest common substring with queries

Revision en2, by Mr.Awesome, 2019-12-13 17:04:01

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.

Tags #strings, substring, #lcs, #hashing

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Mr.Awesome 2019-12-13 17:04:01 7
en1 English Mr.Awesome 2019-12-13 17:03:28 566 Initial revision (published)