Sorry, ignore my post. Its totally broken. 2012/12/19 Andrey Ponomarev <[email protected]>: > 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.
