Skip to content

Commit e2799d8

Browse files
committed
Longest Common Subsequence
1 parent d1c45ac commit e2799d8

File tree

2 files changed

+76
-8
lines changed

2 files changed

+76
-8
lines changed

README.md

Lines changed: 45 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -4,91 +4,116 @@ This is a repository containing various C++ Programs to understand the basic con
44

55
## Programs
66

7+
* [0-1 Knapsack](https://github.com/altruistcoder/Data-Structures/blob/master/01_knapsack.cpp):
8+
9+
C++ Code for solving the 0-1 Knapsack problem using Dynamic Programming approach.
10+
11+
12+
* [Fractional Knapsack](https://github.com/altruistcoder/Data-Structures/blob/master/fractional_knapsack.cpp):
13+
14+
C++ Code for solving the Fractional Knapsack problem using Greedy approach.
15+
16+
17+
* [Longest Common Subsequence (LCS)](https://github.com/altruistcoder/Data-Structures/blob/master/lcs.cpp):
18+
19+
C++ Code for solving Longest Common Subsequence (LCS) problem.
20+
21+
722
* [Queue Implementation](https://github.com/altruistcoder/Data-Structures/blob/master/Queue/queue.cpp):
823

924
C++ Code for implemention of a queue.
1025

26+
1127
* [Queue Using Two Stacks](https://github.com/altruistcoder/Data-Structures/blob/master/Queue/queue_using_stack.cpp):
1228

1329
C++ Code for implementing a queue using two stacks.
1430

31+
1532
* [Queue Using Single Stack](https://github.com/altruistcoder/Data-Structures/blob/master/Queue/queue_using_single_stack.cpp):
1633

1734
C++ Code for implementing a queue using single stack (using recursion).
1835

36+
1937
* [Stack Implementation](https://github.com/altruistcoder/Data-Structures/blob/master/Stack/stack.cpp):
2038

2139
C++ Code for implemention of a stack.
2240

41+
2342
* [Stack Using Two Queues](https://github.com/altruistcoder/Data-Structures/blob/master/Stack/stack_using_two_queues.cpp):
2443

2544
C++ Code for implementing a stack using two queues.
2645

46+
2747
* [Stack Using Single Queue](https://github.com/altruistcoder/Data-Structures/blob/master/Stack/stack_using_single_queue.cpp):
2848

2949
C++ Code for implementing a stack using single queue.
3050

51+
3152
* [Merge Sort](https://github.com/altruistcoder/Data-Structures/blob/master/Sorting%20Programs/merge_sort.cpp):
3253

3354
C++ Code for implementing Merge Sort algorithm.
3455

56+
3557
* [Quick Sort](https://github.com/altruistcoder/Data-Structures/blob/master/Sorting%20Programs/quick_sort.cpp):
3658

3759
C++ Code for implementing Quick Sort algorithm.
3860

61+
3962
* [Randomized Quick Sort](https://github.com/altruistcoder/Data-Structures/blob/master/Sorting%20Programs/quick_sort_randomized.cpp):
4063

4164
C++ Code for implementing Randomized version of Quick Sort algorithm.
4265

66+
4367
* [Insertion Sort](https://github.com/altruistcoder/Data-Structures/blob/master/Sorting%20Programs/insertion_sort.cpp):
4468

4569
C++ Code for implementing Insertion Sort algorithm.
4670

71+
4772
* [Bubble Sort](https://github.com/altruistcoder/Data-Structures/blob/master/Sorting%20Programs/bubble_sort.cpp):
4873

4974
C++ Code for implementing Bubble Sort algorithm.
5075

76+
5177
* [Selection Sort](https://github.com/altruistcoder/Data-Structures/blob/master/Sorting%20Programs/selection_sort.cpp):
5278

5379
C++ Code for implementing Selection Sort algorithm.
5480

81+
5582
* [Recursive Binary Search](https://github.com/altruistcoder/Data-Structures/blob/master/Searching%20Programs/binary_search_recursive.cpp):
5683

5784
C++ Code for implementing Binary Search algorithm recursively.
5885

86+
5987
* [Iterative Binary Search](https://github.com/altruistcoder/Data-Structures/blob/master/Searching%20Programs/binary_search_iterative.cpp):
6088

6189
C++ Code for implementing Binary Search algorithm iteratively.
6290

91+
6392
* [Linear Search](https://github.com/altruistcoder/Data-Structures/blob/master/Searching%20Programs/linear_search.cpp):
6493

6594
C++ Code for implementing Linear Search algorithm.
6695

67-
* [0-1 Knapsack](https://github.com/altruistcoder/Data-Structures/blob/master/01_knapsack.cpp):
68-
69-
C++ Code for solving the 0-1 Knapsack problem using Dynamic Programming approach.
70-
71-
* [Fractional Knapsack](https://github.com/altruistcoder/Data-Structures/blob/master/fractional_knapsack.cpp):
72-
73-
C++ Code for solving the Fractional Knapsack problem using Greedy approach.
74-
7596

7697
* [Parenthesis Balancing](https://github.com/altruistcoder/Data-Structures/blob/master/balanced_parenthesis_check.cpp):
7798

7899
C++ Code for checking the balancing of Parenthesis.
79100

101+
80102
* [Generate Balanced Parenthesis](https://github.com/altruistcoder/Data-Structures/blob/master/generate_parenthesis.cpp):
81103

82104
C++ Code to generate balanced parenthesis of the given order.
83105

106+
84107
* [Decreasing Frequency-Wise Array Sorting](https://github.com/altruistcoder/Data-Structures/blob/master/decreasing_frequency_wise_sorting.cpp):
85108

86109
C++ Code for performing decreasing frequency-wise sorting of a given array.
87110

111+
88112
* [Checking Sorting of Array with atmost One Swapping of Elements](https://github.com/altruistcoder/Data-Structures/blob/master/check_sort_one_swap.cpp):
89113

90114
C++ Code for checking whether it is possible or not to sort the given array by doing atmost one swapping of elements of array.
91115

116+
92117
* [Anti-Clockwise Rotation of Array by 90 ](https://github.com/altruistcoder/Data-Structures/blob/master/90_degree_rotate_matrix.cpp):
93118

94119
C++ Code for rotating the elements of the matrix by 90 degrees in anti-clockwise direction.
@@ -98,50 +123,62 @@ This is a repository containing various C++ Programs to understand the basic con
98123

99124
C++ Code for rotating the elements of the matrix by 90 degrees in clockwise direction.
100125

126+
101127
* [Finding Pair of Elements with given Sum in an Array](https://github.com/altruistcoder/Data-Structures/blob/master/pair_with_given_sum.cpp):
102128

103129
C++ Code for finding the pair of elements in an array whose sum is equal to a particular sum entered by the user.
104130

131+
105132
* [Finding Pair of Elements with given Sum in an Array using Hashing Method](https://github.com/altruistcoder/Data-Structures/blob/master/pair_with_given_sum_hashing.cpp):
106133

107134
C++ Code for finding all the pairs of elements in an array whose sum is equal to a particular sum entered by the user by using the hashing set method.
108135

136+
109137
* [Finding the Pythgorean Triplets present in an Array](https://github.com/altruistcoder/Data-Structures/blob/master/find_pythagorean_triplet_in_array.cpp):
110138

111139
C++ Code for finding the triplet of elements present in an array which act as a Pythagorean Triplet.
112140

141+
113142
* [Generating the Pythgorean Triplets till a particular Limit](https://github.com/altruistcoder/Data-Structures/blob/master/generate_pythagorean_triplet.cpp):
114143

115144
C++ Code for generating the Pythagorean Triplets having values less than a limit entered by a user.
116145

146+
117147
* [Number Occurring Odd no. of Times in an Array](https://github.com/altruistcoder/Data-Structures/blob/master/number_occurring_odd_times.cpp):
118148

119149
C++ Code for finding the number which occurs odd no. of times in the given array.
120150

151+
121152
* [Largest Contiguous Sum in an Array](https://github.com/altruistcoder/Data-Structures/blob/master/largest_contiguous_array_sum.cpp):
122153

123154
C++ Code for finding the largest contiguous sum present in the given array.
124155

156+
125157
* [Segregate 0s and 1s in an Array](https://github.com/altruistcoder/Data-Structures/blob/master/segregate_0_1.cpp):
126158

127159
C++ Code for segregating 0s and 1s in the given array.
128160

161+
129162
* [Second Largest Element in an Array](https://github.com/altruistcoder/Data-Structures/blob/master/second_largest_in_array.cpp):
130163

131164
C++ Code for finding the second largest element present in the given array.
132165

166+
133167
* [First Non-Repeating Character in an String](https://github.com/altruistcoder/Data-Structures/blob/master/first_non_repeating_character.cpp):
134168

135169
C++ Code for finding the first non-repeating character present in the given string.
136170

171+
137172
* [Remove Duplicates from a Sorted Array](https://github.com/altruistcoder/Data-Structures/blob/master/remove_duplicates_sorted_array.cpp):
138173

139174
C++ Code for removing duplicate elements present in a sorted array.
140175

176+
141177
* [Check Binary Representation of a number is Palidrome or not](https://github.com/altruistcoder/Data-Structures/blob/master/binary_palindrome.cpp):
142178

143179
C++ Code for checking whether binary representation of a number is palindrome or not.
144180

181+
145182
* [Check whether two strings are anagrams of each other](https://github.com/altruistcoder/Data-Structures/blob/master/check_anagrams.cpp):
146183

147184
C++ Code for checking whether two given strings are anagrams of each other.

lcs.cpp

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
#include <iostream>
2+
#include <string.h>
3+
4+
using namespace std;
5+
6+
int lcs(char x[],char y[])
7+
{
8+
int i, j, m=strlen(x), n=strlen(y), r[m+1][n+1];
9+
for(i=0; i<=m; i++)
10+
{
11+
for(j=0; j<=n; j++)
12+
{
13+
if (i==0 || j==0)
14+
r[i][j]=0;
15+
else if(x[i-1]==y[j-1])
16+
r[i][j]=r[i-1][j-1]+1;
17+
else
18+
r[i][j] = max(r[i-1][j], r[i][j-1]);
19+
}
20+
}
21+
return r[m][n];
22+
}
23+
24+
int main()
25+
{
26+
char x[50], y[50];
27+
cout<<"Enter the two strings: ";
28+
cin>>x>>y;
29+
cout<<"The length of the longest common subsequence is: "<<lcs(x, y);
30+
return 0;
31+
}

0 commit comments

Comments
 (0)