-
Notifications
You must be signed in to change notification settings - Fork 365
/
Shortest Common Supersequence Problem.cpp
39 lines (32 loc) · 1.24 KB
/
Shortest Common Supersequence Problem.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*The Shortest Common Supersequence (SCS) is finding the shortest supersequence Z of given sequences X and Y such that both X and Y are subsequences of Z.
The problem differs from the problem of finding the shortest common substring. Unlike substrings, subsequences are not required to occupy consecutive positions within the original string.*/
#include <iostream>
#include <string>
using namespace std;
// Function to find the length of the shortest common supersequence of
// sequences `X[0…m-1]` and `Y[0…n-1]`
int SCSLength(string X, string Y, int m, int n)
{
// if the end of either sequence is reached, return
// the length of another sequence
if (m == 0 || n == 0) {
return n + m;
}
// if the last character of `X` and `Y` matches
if (X[m - 1] == Y[n - 1]) {
return SCSLength(X, Y, m - 1, n - 1) + 1;
}
else {
// otherwise, if the last character of `X` and `Y` don't match
return min(SCSLength(X, Y, m, n - 1) + 1,
SCSLength(X, Y, m - 1, n) + 1);
}
}
int main()
{
string X = "ABCBDAB", Y = "BDCABA";
int m = X.length(), n = Y.length();
cout << "The length of the shortest common supersequence is "
<< SCSLength(X, Y, m, n);
return 0;
}