Lightoj 1110 (An Easy LCS) >> To Find Out Lexicographically Smallest LCS String .... Help Please !!!
Two string will be given. I've to find out lexicographically smallest LCS string. I have coded one, but it is giving me WA... I tried with some cases, but failed to find out the problem. Would anyone help please ???
I just need the case for which case my code is failed... Please help ... :(
My code is here
Problem Link is here
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
I have no idea why you use so many pointers and char arrays and moreover why you pass it to one of your functions (I'm sure if you pass the test you have WA currently u'll get TLE due to many
strcpys).I would just reverse strings and make DP[][] and B[][] matrices (see CLRS for details) and if s1[i]!=s2[j] and DP[i-1][j] is equal to DP[i][j-1] choose lexicographically smaller.
Lastly, using B[][] determine the answer and reverse it.
As there can be at most 100 character in a string, I thought that would not be a problem... :(
And if I don't do wrong calculation, my code's complexity is O(n^3)... Will it give TLE for n=100 in online judge like lightoj ??? It's sure if it is spoj, I'll never like to do so... :)
If I do any wrong, please show me... :(
it's wrong to copy all string when you are at some level of recursion. use
string DP(int i1, int i2);if (res.size() < t.size() || res.size() == t.size() && res > t) res = t;Actually I tried with return type string too...
But when I return a string to a level, the level I want to send, receive a null string always...
So I was compelled to do so.. :(
May be my implementation can be wrong... :/
Anyway, would you tell me please, what is the problem when I copy a string in different level of a recursion... Is it problem too, if I use pointer ???
Please, let me known... :(
beacause there can be bad remembered prefix of optimal answer. for example LCS length is 5 at some step of recursion you have prefix "ba" and remeber for this i1 = 42 and i2 = 66 dpc[i1][i2] = "ba???" then at some step you have prefix "ab", but when you step in remembered state i1 = 42 and i2 = 66 you rewrite all the answer with bad prefix "ba". it is bad because "ab" is better.
code
why you reverse strings?
I've not reversed any string...
If you tell about 92 & 93 number line what I've done is,
when ch1[i]==ch2[j], I've firstly stored this character in st1[0], then kept all characters of res string in st1.
That's all... :)
my comment is adressed to this comment
Ow... Sorry ... :)
Well, because I don't want to compare whole strings (current answers), so I greedily compare only last characters of them. In other words it means I put more importance on last characters which is obviously incorrect, but it should work for reversed strings because there I do want that initial characters be more important.
But interestingly enough this idea (or I hope implementation of it) is getting WA too :D :D
I tried this approach too.but this approach fails cases when immediate matched character is same and better solution can be found in depth.