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

hide comments
mrinal_aich: 2017-05-26 10:45:33

Space and Time Efficient LCS Problem.

Last edit: 2017-05-26 11:09:12
lukaszpolska: 2017-02-10 17:38:23

vishals: Maybe you using to much memory. You should have dp[2][50100] not dp[50100][50100]

vishals: 2016-05-28 17:40:52

Why in c++ its giving me SIGSEGV . The code is working fine on ideone and gcc compiler.

ysharp: 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
ysharp: 2015-09-24 23:21:26

Interesting problem, for the run-time constraints. I'll try to tackle it in C#.

alok singh: 2015-09-21 21:42:15

Last edit: 2015-09-22 13:49:50
draco: 2015-05-26 13:54:16

@kotsos
have the same problem. Code runs on spoj as well as gcc smoothly but gives sigsegv on spoj :(

bholagabbar: 2015-04-19 11:46:52

Evil, Evil problem

kotsos: 2015-04-09 21:29:21

I have a segmentation fault (SIGSEGV) when I submit my code at SPOJ in C++, but not in ideone where I have a success and a correct answer returned. Can someone suggest something?

Last edit: 2015-04-10 17:52:57
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?


Added by:Tooru Ichii
Date:2012-08-25
Time limit:0.676s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Folklore