SPOJ.com - Problem LCS0

LCS0 - Longest Common Subsequence

#lcs

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

Submit solution!

hide comments



	x320200: 2024-08-30 19:48:18 First ever PyPy3 AC on this one! Don't be discouraged :) (but not easy at all, yes)
	mj_oppo: 2022-07-11 10:56:23 Ignore the problem if you are using Python3/PyPy3.
	eric7237: 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...
	phoemur: 2018-11-11 00:07:04 Evil problem. Google [spoiler] algorithm and learn something new Last edit: 2018-11-11 00:27:57
	ysharp: 2015-09-25 00:19:26 I'm not sure yet, but there might be a solution in O(Max(Mlog(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*
	ysharp: 2015-09-24 23:21:26 Interesting problem, for the run-time constraints. I'll try to tackle it in C#.
	bholagabbar: 2015-04-19 11:46:52 Evil, Evil problem
	Encho: 2014-12-27 00:37:41 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?
	Siarhei Kulik: 2014-10-18 00:24:57 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
	Damian Straszak: 2012-08-26 07:55:22 and now look at the constraints here and there

Submit solution!

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