EELCS - Easy Longest Common Subsequence

no tags 

A common subsequence between two strings A and B is defined as 2 sets { i0 , i1 , i2 , i3 , ... , ik } { j0 , j1 , j2 , j3 , ... , jk } such that 0 <= i0 < i1 < i2 < i3 < ... < A.length() and 0 <= j0 < j1 < j2 < j3 < ... < B.length() and A[ i0 ] = B[ j0 ], A[ i1 ] = B[ j1 ] , ... , A[ ik ] = B[ jk ]. Given two strings A and B print the length of the longest common subsequence between them.

i.e. "a", "d","cd" are common subsequence between the two strings "abcd" and "adcd" while "acd" is the longest common subsequence between them.

Input

First line contains a string A (1 <= A.lenth() <= 7).

Second line contains a string B (1 <= B.length() <= 7).

Each string is composed of lower case letters only ('a' -'z').

Output

Prints one line containing the length of the longest common subsequence.

 

Example

Input:
abcd
adcd

Output:
3

hide comments
gaurav_2000: 2018-06-05 09:24:57

AC in one go

imkiller: 2018-03-24 21:20:13

Just a simple dp approach .
AC in 1 Go .

vivace: 2016-10-16 15:57:28

there is only one test case

hacker_daante: 2015-05-23 21:30:59

<p>nice</p>

Devashish: 2014-10-06 13:36:37

till when do we take the input.

EDIT: Got it ..thanks a lot for this problem :)
ANS:
while(scanf("%s",&s1)!=EOF && scanf("%s",&s2)!=EOF)
in c++
for those who are not getting it.

Last edit: 2014-10-06 13:45:03

Added by:Omar ElAzazy
Date:2012-03-17
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64