The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows. The first input line of each test case contains two space-separated Strings “STR1” and “STR2” representing two Strings.
For each test case, print the length of the longest common subsequence. Print the output of each test case in a separate line.
You are not required to print the expected output; it has already been taken care of. Just implement the function.
1 <= T <= 50 1 <= |STR1| <= 10^2 1 <= |STR2| <= 10^2 Where |STR1| and |STR2| denote the length of “STR1” and “STR2” respectively. Time Limit: 1 sec
The basic idea of this approach is to break the original problem into sub-problems. Let us assume we want to find the length of the longest common subsequence of “STR1” and “STR2” whose length is ‘N’ and ‘M’ respectively.
Now, let us define a recursive function
LCS(Int I, int J, string STR1, string STR2)
Which returns the length of the longest common subsequence of string STR1[0: I-1] and STR1[0: J-1] where STR1[l: R] denotes the substring of “STR1” having characters from index ‘l’ to index ‘R’.
Now, consider the following steps :