Question

Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase.

Input Format

First line of input contains 'n', size of first string. Second line of input contains 'm', size of second string. Third line of input contains string s1. Fourth line of input contains string s2.

Constraints

1<=size(str1),size(str2)<=103

Output Format

Print the length of longest subsequence present in both of them.

Sample Input 0

6
6
ABCDGH
AEDFHR
Sample Output 0

3
Sample Input 1

3
2
ABC
AC
Sample Output 1

2

Answer 1

Answer:

the answer of the question is

Kaisa lga mera majak

Answer 2

Answer:

The code and outputs for the given question are given below:

CODE     ------>

# Python program for finding  the length of longest subsequence present in two given sequences.

def ls(X, Y, m, n):

   if m == 0 or n == 0:

       return 0

   elif X[m-1] == Y[n-1]:

       return 1 + ls(X, Y, m-1, n-1);

   else:

       return max(ls(X, Y, m, n-1), ls(X, Y, m-1, n));

# Verifying the written code with the given sample inputs

# Sample Input 0

X = "ABCDGH"

Y = "AEDFHR"

print ("Sample output: Length of longest subsequence is ", ls(X , Y, len(X), len(Y)) )   # Applying the print command for getting the output

# Sample Input 1

X = "ABC"

Y = "AC"

print ("Sample output: Length of longest subsequence is ", ls(X , Y, len(X), len(Y)) )    # Applying the print command for getting the output

OUTPUT    -------->

Sample output 0: Length of longest subsequence is  3

Sample output 1: Length of longest subsequence is  2

#SPJ3