Question
Download Solution PDFConsider the following two sequences :
X = < B, C, D, C, A, B, C >
and Y = < C, A, D, B, C, B >
The length of longest common subsequence of X and Y is :
Answer (Detailed Solution Below)
Detailed Solution
Download Solution PDFConcept:
If there is match, A[i, j] = A[i – 1, j – 1] + 1
If not match: max(A[i – 1, j], A[i, j – 1])
CALCULATION
Let M = length of X and N = length of Y
int dp[N+1][M+1]
Table of longest common subsequence:
|
X → |
B |
C |
D |
C |
A |
B |
C |
|
|
Y ↓ |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
C |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
A |
0 |
0 |
1 |
1 |
1 |
2 |
2 |
2 |
|
D |
0 |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
|
B |
0 |
1 |
1 |
2 |
2 |
2 |
3 |
3 |
| C | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
|
B |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
The length of longest common subsequence of X and Y = A[N][M] = 4
Last updated on Jun 6, 2025
-> The UGC NET Exam Schedule 2025 for June has been released on its official website.
-> The UGC NET Application Correction Window 2025 is available from 14th May to 15th May 2025.
-> The UGC NET 2025 online application form submission closed on 12th May 2025.
-> The June 2025 Exam will be conducted from 21st June to 30th June 2025
-> The UGC-NET exam takes place for 85 subjects, to determine the eligibility for 'Junior Research Fellowship’ and ‘Assistant Professor’ posts, as well as for PhD. admissions.
-> The exam is conducted bi-annually - in June and December cycles.
-> The exam comprises two papers - Paper I and Paper II. Paper I consists of 50 questions and Paper II consists of 100 questions.
-> The candidates who are preparing for the exam can check the UGC NET Previous Year Papers and UGC NET Test Series to boost their preparations.