Spatzist Relevant Wikipedia article: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
A straightforward solution uses O(n^2) time and space. Optimizations can reduce both of these.
neverloseks so much thanks for your link... i'm in hell before reading the wiki... i have to learn more on dynammic programming....
saru_sweety99 Thank you sooo much for this link.It helped me a lot.
markestudillo Thank you for the link! Really helped understand the concept of obtaining the LCS.
it_henrik thanks for the link, I had stubbornly been banging my head on this one for quite a while (some days) before checking in here :)
So if someone else is struggling with their python3 solution here is mine with explanations on what is happening and why.
To see the sequence of letters just uncomment the lines working on the lcs_letters matrix, it wont pass all tests though
def commonChild(s1, s2): # row 0 = 0, column 0 = 0 l1 = len(s1) l2 = len(s2) # we only need history of previous row lcs = [[0]*(len(s1)+1) for _ in range(2)] #lcs_letters = [['']*(len(s1)+1) for _ in range(2)] # i in s1 = i+1 in lcs for i in range(l1): # get index pointers for current and previous row li1 = (i+1)%2 li = i%2 # j in s1 = j+1 in lcs for j in range(l2): # i and j are used to step forward in each string. # Now check if s1[i] and s2[j] are equal if s1[i] == s2[j]: # Now we have found one longer sequence # than what we had previously found. # so add 1 to the length of previous longest # sequence which we could have found at # earliest previous position of each string, # therefore subtract -1 from both i and j lcs[li1][j+1] = (lcs[li][j] + 1) #lcs_letters[li1][j+1] = lcs_letters[li][j]+s1[li] # if not matching pair, then # get the biggest previous value elif lcs[li1][j] > lcs[li][j+1]: lcs[li1][j+1] = lcs[li1][j] #lcs_letters[li1][j+1] = lcs_letters[li1][j] else: lcs[li1][j+1] = lcs[li][j+1] #lcs_letters[li1][j+1] = lcs_letters[li][j+1] #print(lcs_letters[(i+1)%2][j+1]) return lcs[(i+1)%2][j+1]
WittyNotes Thank you so much. Been beating my brains over this, and it's nice to know that it's a common problem in Computer Science.
puneetkaur Idk what is messed up with this :
#!/bin/python3 def lcs(str1, str2): arr = [[0]* len(str1)]*len(str2) for i in range(len(str2)): for j in range(len(str1)): if i==0 or j==0: if str2[i]==str1[j]: arr[i][j]=1 else: arr[i][j]=0 else : if str2[i]==str1[j] : arr[i][j] = arr[i-1][j-1]+1 else : arr[i][j] = max(arr[i-1][j], arr[i][j-1]) # print(arr[i]) return arr[-1][-1] str1 = input().strip() str2 = input().strip() print(lcs(str1, str2))
mywork_koder You have problem with filling the first row and first line For example You have 2 strings AXX AYY
Expected long_common_sequence_table for first row and line is:
1 1 1 1 1
Acual long_common_sequence_table for first row and line is: 1 0 0 0 0
umyarovrr @puneetkaur, are you sure you want to define your
arrthis way?arr = [[0]* len(str1)]*len(str2)will actually give you a list with n same lists. Take a look:arr = [[0] * 2]*2
print(arr)
[[0, 0], [0, 0]]
arr[1][1] = 1
print(arr)
[[0, 1], [0, 1]]
Sorry, if its irrelevant. Just I am new to python and faced this problem myself
Sirius19 Thank you, you save me
malika_messaoud1 Thank you so much Spatzist this link is really helpful even if i didn't understand the whole article but i understant the essatial, because there a lot of details.
prabhjeet6 thanks man, i have forgotten all that too quickly
ejubkadric In case you want to get to the point and avoid unnecessary info on wikipedia, check out this video: https://www.youtube.com/watch?v=NnD96abizww It explains how to solve the longest common subsequence problem. Using that I was able to implement a solution to this problem. Cheers :)
1634810123_coe3b Did all test cases pass? I am getting timeout in 4 in python.
rdn32 Using Python, I was having some trouble getting test case #5 running sufficiently quickly to pass. One of my problems was to do with unnecessarily making the memory use quadratic in the problem size, but that's kind of an algorithm problem. The other is specific to Python, and is a bit subtle so I thought it would be worth describing: although the program can be written without defining a function to do the work (as it only needs to solve one case), accessing file scope variables is slower than function scope variables. Once you've got the algorithm right, this second issue makes a surprising amount of difference to performance.
scotthellam Thanks! That made enough of a difference to pass test #5.
ygh929 Thanks! your comment helps a lot to pass test #5!
prashant_93_y @rdn32, @scotthellam, @ygh929 can you guys please tell me how to optimize my code to pass 5th test case http://ideone.com/PmRSaA
opanon That looks fine to me. Are you still having issues?
cyestoner I ran into this problem with python3. Using python2 "Worked For Me".
Some digging on the issue makes me think that there are some performance problems with list indexing on python3 that might cause enough of a slowdown to fail the 10s timer.
SidSam I'm using Python2 too, but using that code, 5 test cases terminate due to timeout. Test cases 9 to 13.
arpitvarshney Apply DP. Its not required to generate the full matrice as we need only two rows at a time. That may give a hint.
jake_griffin Yes, and you don't even need two rows. I used one row, and saved the last overwritten value in another variable. The part of the row "to the left" of current processing posision was like your "row 2", and the part of the row "to the right" was like your "row 1". The extra variable was to store the number that was last overwritten from row 1.
cakaroo Using 2 raw it works in Python 2 but not in python 3.
Varun_Rathi0623 yes for me too how did you solved them
subashm6 [deleted]
gregory_geller I would have never figured out why I was timing out in case #5 without this hint. Where can I find out more about the relative performance of file scope vs function scope in python?
TonyKim I wouldn't have figure out why I was timing out without this hint too. I would be also interested with any references about file scope vs function scope
TonyKim I found some details about the reason why function scope is faster! http://http://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function
akshayc11 I am unsure what you mean by this. I am not an expert python programmer. Could you suggest further sources / examples where I can read up on what you mean? I created a function as described, with the non-recursive version of the algorithm. However, I am still facing the timeout issue in case 5. I am also using O(2m) additional memory.
Are there any other optimizations that I am missing?
aneeshkher What is the time complexity of your solution? It should not exceed O(mn).
akshayc11 It does not. It is O(mn)
shravanc6 I was surprised that moving my code into a function solved TLE for last 5 test cases. Had a hard time figuring this out, but I see that rdn32 has already mentioned it. Something I learned today.
emir13 Wow! Interesting, thanks!
emir13 Its really interesting! while same code only passes half of the test cases with Python3, with Python2 it passes all test cases. Why it differs that much? Any answer is appreciated!
rwan7727 In c++:
string s1; cin >> s1; string s2; cin >> s2; // matrix c stores the char count of child string vector < vector<int> > c(s1.length()+1,vector<int>(s2.length()+1)); for (int i=1;i<=s1.length();i++) { for (int j=1;j<=s2.length();j++) { if (s1[i-1]==s2[j-1]) c[i][j]=c[i-1][j-1]+1; else c[i][j]=max(c[i][j-1], c[i-1][j]); } } cout << c[s1.length()][s2.length()];vickaboy bottom up works perfectly but TLE in top down memoization approaches
hacker_khan why using dynammic array in c++ solves the issue of timeout??
alimobasshir21 same doubt, segmentation faults if array is used in place of vectors.
Khalil_ammar vectors are stored in the heap while statically declared arrays are stored in the stack. Since the programs are uploaded and tested, the stack allocated for your program is not enough to store a 5000x5000 array.
boiko_ivan You don't need to store 5000 x 5000 array.
You only need to keep 2 rows, last and previous.
shallymittal08 Thanks, replacing array with vector helped a lot.
woldegebrielkeb1 [deleted]woldegebrielkeb1 [deleted]
sharmajikalaunda Thank you so sooo much!!!!
shishirsharma Also keep poping old rows from memo which are not needed any more.
19998sachinyadav python2 works fine but python3 gives TLE.......!
Tsukuyomi1 If you get timeout in Python just submit the same solution in PyPy. My code timed out for 6 testcases in Python 3 but got accepted with max time 0.51s in PyPy3
so_no Indeed. That's pretty weird.
songzy12 Thanks!
max_waser Bless you!
boiko_ivan Indeed so.
Kept banging my head against the keyboard for a couple of days...
Even invented algorithm faster than N^2 using binary trees, which was much faster on smaller strings, but was 4 times slower on 5000 length.Then gave up and looked at Discussion :)
nonomus Anyone who is getting the segfault error on test case #5: You are likely programming in C/C++ and are running out of stack space for your array. Use dynamic memory to fix it.
FilipeGoncalves No need to use dynamic memory. Max string size is 5000. Just use a big statically allocated array.
shanur_cse_nitap FilipeGoncalves i solved it using dynamic programming and it passed all test cases .
but i would be glad to know your approach
super4166 i am trying to solve it using longest common subsequence but segmention fault is coming in few cases
utkarshpp U can solve this program by using array of size 2 by min(s1.size(),s2.size())
it won't give segmentation fault Most probably its SIGSEGV, Segmentation fault bcoz of invalid memory pointer reference
ashwinmanoj95 I tried allocating dynamic memory and also increasing the stack space using pragma directive and still my program shows segmentation fault for the fifth test case. can anyone pls help me..thank you
abhishek22 Instead of defining 2d matrix inside a function, define it globally. In this way it will acquire data segment instead of stack memory.
shivalikranaut you just solved my so many problems. Thank you
maverick55 Thanks man. You saved my day.
ppg_0007 oh thanks it helped me..
luckykohli Thanks a lot man
the_piranha Thanks a tonne , you saved my day.
ashishkaila Dynamic memory is not the correct way to handle this. The correct way is to use an iterative solution rather than the recursive solution.
ayushmw1 Need to make dp array global. I don't understand how that solves the problem but it does.
gratitude when u use declare globally it will use stack memory but when u declare it locally it cannot use stack memory and it will only use heap memory which is not enough for the 5th test case..so segfault is expected :)
sheep0x C/C++ local vars, unless declared “
static”, (typically) use stack memory or register or simply disappear at compile time.Dynamic allocation (typically) uses heap area.
Global vars and static local vars and static member vars (typically) use a separate “static” memory area. (If you initialize them to zero and never use them, chances are OS doesn't even allocate memory for them.)
(Terminology differs from tutorial to tutorial but the idea is that there is a separate, pre-allocated part of virtual memory that is neither stack nor heap.)
See w:Data segment and cppreference:storage duration for more details. If you have a Linux box, you can also try toying with stack limit using
ulimit(assuming you are using Bash/Zsh).
MystikNinja The same change solved it for me as well.
RryLee like this
int **array = new int*[length + 1]; for (int i = 0; i < length + 1; ++i) { array[i] = new int[length + 1]; }
manish_pal Dynamic allocation of 2D array helped me pass all the test cases. Thanks.
v_balazs My solution is based on the following article from wikipedia: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
public class Solution { static int commonChild(String a, String b){ int[][] C = new int[a.length()+1][b.length()+1]; for (int i = 0; i < a.length(); i++) { for (int j = 0; j < b.length(); j++) { if (a.charAt(i) == b.charAt(j)) { C[i+1][j+1] = C[i][j] + 1; } else { C[i+1][j+1] = Math.max(C[i+1][j], C[i][j+1]); } } } for (int i = 0; i < a.length(); i++) { } return C[a.length()][b.length()]; } public static void main(String[] args) { Scanner in = new Scanner(System.in); String s1 = in.next(); String s2 = in.next(); int result = commonChild(s1, s2); System.out.println(result); } }
houqisen Thanks for sharing. I am studying on this solution.
h674734481 Nice try，Thx
dsun092 For anyone having trouble passing TLE using DP in python2, if you are using the max function, try swapping that out for if else statement... thanks cucux for pointing it out!
Samuel_Russell This was helpful to me. No idea why max is so much slower than else if.
Liviul Same problem in Python3: eliminate it and it goes fast enough.
sigbusyff I'm a little bit surprised there's only 30 points up for grabs for this one. It's got a very low success rate, and would arguably be more at home in the "Dynamic Programming" area...
whoan Agree with you @sigbusyff. On the other hand, the "Resources" section give good hints about how to solve the problems. In this particular exercise, "Dynamic Programming Basics" is in the list BTW.
olegcherednik static int commonChild(String s1, String s2) { int[][] arr = new int[s1.length() + 1][s2.length() + 1]; for (int i = 0; i < s1.length(); i++) for (int j = 0; j < s2.length(); j++) arr[i + 1][j + 1] = s1.charAt(i) == s2.charAt(j) ? arr[i][j] + 1 : Math.max(arr[i][j + 1], arr[i + 1][j]); return arr[s2.length()][s1.length()]; }
meet_lovelyac Hi. why are you keeping the size of arr as s1.length()+1 and s2.length()+1?
sardanagautam121 watch this, you will understand : https://www.youtube.com/watch?v=sSno9rV8Rhg
sumanconstantin Because you need to work with previous values.
That's why the first values are all '0' on both the line and column, and the value sums start from indeces 1 and 1.
arr[i + 1][j + 1]
That's why you need to allocate an extra cell for both line and column.
cool_shark Variation of LCS by using two alternating rows instead of a full list and by replacing
maxwithif elseto avoid time-out errors.def commonChild(s1, s2): m, n = len(s1), len(s2) prev, cur = [0]*(n+1), [0]*(n+1) for i in range(1, m+1): for j in range(1, n+1): if s1[i-1] == s2[j-1]: cur[j] = 1 + prev[j-1] else: if cur[j-1] > prev[j]: cur[j] = cur[j-1] else: cur[j] = prev[j] cur, prev = prev, cur return prev[n]
shvburade I tried still 6 timeouts, python 3
Sort 279 Discussions, By:
Please Login in order to post a comment