How can i print all different LONGEST COMMON SUB-SEQUENCE(LCS) of two different string.
How can i print all different LONGEST COMMON SUB-SEQUENCE(LCS) of two different string.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 165 |
3 | adamant | 161 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | orz | 146 |
9 | SecondThread | 145 |
9 | pajenegod | 145 |
Название |
---|
need NxM matrix,where ans[i][j] is answer from first string with length i and second string with length j,then if a[i]=b[j]; ans[i][j]=ans[i-1][j-1]+1; else ans[i][j]=max(ans[i-1,j],ans[i,j-1]); and length of LCS will be in ans[n][m]; and for finding all different LCS go to from ans[n,m] back:
sorry for my poor english.
thanks for reply. if string A="abcd" and string B="acbd" .Here,LCS will be abd and acd both. If i want to print both of them,how can i do that? By the above process u described, i can't print both of them. PLEASE HELP.
you can use dfs(i,j,s) where i and j is indexes of Matrix and s is length of answer way:
and in main program when you have got ANS matrix then you can go to dfs(n,m,1); and this dfs go output both of them.sorry for my poor english again :)
you can do this:
M[i][j] is the matrix, sol is the subsequence and l1 and l2 are the length of both strings s1 and s2. Also the length of the subsequence is M[l1-1][l2-1].
no this doesn't work it adds a char to the answer even it's not in the solution
After the lasha explain you can try this problem TRIP
can anybody please give the recursive soln of printing all LCS ?? i did LCS recursively,,i can print LCS any 1 bt can't get any way how to print all LCS recursively
here