I think you can try the following. First, for each lowercase latin letter prepare an array of its indexes in the second string. Overall length is O(m) and the time is also O(m). Then, let the 'state' be two values for each lowercase latin letter: maximal subsequence length, ending with this letter and the leftmost position in the second string where this maximal subsequence ends. Initially set the state for each letter for (0,-1). Then, update the state for each prefix of the first string from prefix of length 1 to the whole string. At each step you have l_i - current letter in the first string, and state S. Try to update maximal length S[l_i] based on all possible last letters by binary searching array of indexes for allowed position of l_i with minimal index (i.e. leftmost). It gives you complexity O(n*c*log(m)). Where c stands for alphabet size.
2012/12/16 anupsingh <[email protected]>: > hey can any one tell me the optimized method of solving LCS problem. I hv > optimized still it show TLE... > here is the link > www.spoj.com/problems/LCS0/ > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msg/google-code/-/v4Fmk_-athsJ. > For more options, visit https://groups.google.com/groups/opt_out. > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
