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
flyingduchman_: 2018-04-05 17:22:52

No country for O(MN) [O(N)space] guys.
There is a O(RlogN) algorithm , where R is a special parameter that can be bigger than MN, but in many cases it's small enough.
the algorithm is mentioned in Algorithms on Strings, Trees and Sequences by Dan Gusfield.
Or, serarch codeforces LCS0, many people discussed about it.
Or, solve uva-10405 or similar oj problems.

Last edit: 2018-04-06 07:48:49
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

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