| Submit | All submissions | Best solutions | Back to list |
LCS0 - Longest Common Subsequence |
No imagination at the moment.
Input
You will be given two lines. The first line will contain the string A, the second line will contain the string B. Both strings consist of no more than 50000 lowercase Latin letters.
Output
Output the length of the longest common subsequence of strings A and B.
Example
Input
abababab bcbb
Output
3
| Added by: | Sergey Kulik |
| Date: | 2012-08-25 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Folklore |
hide comments
|
2024-08-30 19:48:18
First ever PyPy3 AC on this one! Don't be discouraged :) (but not easy at all, yes) |
|
|
2022-07-11 10:56:23
Ignore the problem if you are using Python3/PyPy3. |
|
|
2018-12-29 17:00:45
Wow, that was not easy. I was able to solve it via the bit string LCS argorithm here -- http://users.monash.edu/~lloyd/tildeStrings/Alignment/86.IPL.html That paper includes C code, though I admit I don't understand the bit manipulation magic... |
|
|
2018-11-11 00:07:04
Evil problem. Google [spoiler] algorithm and learn something new Last edit: 2018-11-11 00:27:57 |
|
|
2015-09-25 00:19:26
I'm not sure yet, but there might be a solution in O(Max(M*log(N), N)) where M <= N. Granted, though, for now, odds are still good I'm completely wrong, eventually. Last edit: 2015-09-25 00:24:41 |
|
|
2015-09-24 23:21:26
Interesting problem, for the run-time constraints. I'll try to tackle it in C#. |
|
|
2015-04-19 11:46:52 bholagabbar
Evil, Evil problem |
|
|
2014-12-27 00:37:41 Encho
This seems like a really cool problem. Even wikipedia page for LCS mentions no algorithm faster than O(NM). So that made me wonder, is the intended algorithm something the author come up with, some cool trick, or is it based off of some long and tough scientific paper as some other difficult problems on SPOJ are? |
|
|
2014-10-18 00:24:57 Siarhei Kulik
OK, just to make it clear and to avoid further questions regarding complexity. No, O(NM) or O(N^2) or anything similar will not pass. Maybe, you'll find a way to get AC with some heuristics but I believe, it's very hard. Generally, I don't know any good heuristic for the problem. Also, there exists an O(NlgN+ClgN) algo or something similar. We don't have any constraint on C so, this solutions also will fail. But the fact that some coders got AC and their solutions are in fact similar to mine proves that the algo exists and it is possible to come up with it. Last edit: 2012-10-22 18:55:00 |
|
|
2012-08-26 07:55:22 Damian Straszak
and now look at the constraints here and there |
RSS