The LCS problem is the problem of finding the longest subsequence in a given set of sequences. However, elements of subsequence doesn’t have to be a continous part of original sequence (check out sample input and output).
Read more on wikipedia.
Input
a(1)a(2) ... a(n) b(1)b(2) ... b(m)
a(x), b(x) – elements of given sequences
Sample input
asbaaababa saababx
Sample output
saabab
Complexity
In the following solution there are two nested loops, so the algorithm runs in Θ(len1 · len2) time.
Source code
|
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <iostream> #include <string> using namespace std; struct Field { char c; int length; Field * previous; }; int main() { //get strings string s1, s2; cin >> s1; cin >> s2; //get lengths int len1 = s1.length(); int len2 = s2.length(); //init array Field ** lcs = new Field*[len1 + 1]; for (int i = 0; i <= len1; i++) { lcs[i] = new Field[len2 + 1]; for (int j = 0; j <= len2; j++) { lcs[i][j].c = '\0'; lcs[i][j].length = 0; lcs[i][j].previous = NULL; } } //dynamic for (int idx1 = 1; idx1 <= len1; idx1++) { for (int idx2 = 1; idx2 <= len2; idx2++) { if (s1[idx1 - 1] == s2[idx2 - 1]) { lcs[idx1][idx2].c = s1[idx1 - 1]; lcs[idx1][idx2].length = lcs[idx1 - 1][idx2 - 1].length + 1; lcs[idx1][idx2].previous = &lcs[idx1 - 1][idx2 - 1]; } else if (lcs[idx1 - 1][idx2].length > lcs[idx1][idx2 - 1].length) { lcs[idx1][idx2].length = lcs[idx1 - 1][idx2].length; lcs[idx1][idx2].previous = &lcs[idx1 - 1][idx2]; } else { lcs[idx1][idx2].length = lcs[idx1][idx2 - 1].length; lcs[idx1][idx2].previous = &lcs[idx1][idx2 - 1]; } } } //result string result; Field * current = &lcs[len1][len2]; while (current) { if (current->c != '\0') result = current->c + result; current = current->previous; } cout << result.c_str(); return 0; } |
