Find the length of the longest common substring with queries

Правка en2, от 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.

Теги #strings, substring, #lcs, #hashing

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Mr.Awesome 2019-12-13 17:04:01 7
en1 Английский Mr.Awesome 2019-12-13 17:03:28 566 Initial revision (published)