I am trying to solve a problem where I am given 2 strings A and B. Length of A is n and length of B is m. Now, q queries need to be answered. Each query will consist of 2 integers i and j such that 1 <= i,j <= n. For each such query, I want to find the length of the longest common sub-sequence of A.sub_string(i, j) and B.
Constraints:
1 <= n <= 10^4
1 <= m <= 10^4
1 <= Q <= 10^2
Time Limit: 3 seconds
LCS works in O(nm), with Q queries it will be O(Qnm).
This will perform 10^10 operations which will not pass the time limit.
https://arxiv.org/pdf/0707.3619.pdf — with such technique you can find "the whole a against every substring of b(string-substring LCS);" (p.45) in O(NM) time, if I'm not wrong.
Btw, LCS can be solved in O(N*M/word+|alphabet|*max(N,M)/word), it will be squeezable enough for lowercase/uppercase letters with machine word ~ 64 ~ 10^10/64 operations. It described here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.6017 Bonus: you can speed it up with method of Four Russians
Thanks mgcd.