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.