Longest Common Subsequence in C++
May 25, 2007 Leave a comment
Simple program that efficiently finds the longest common subsequence of two sequences, written in C++ using dynamic programming. Unforunately, there are probably many bugs, but for what I needed it for it seems to work.
I should probably add that the reason this is complicated is because it is efficient and uses dynamic programming (sacrificing storage space for computation time). It’s not a stupid brute force like how it could be done with a regex and a couple loops.
Here is the Header:
#include <iostream> #include <string> using namespace std; #ifndef LCS_FUNCTIONS_H #define LCS_FUNCTIONS_H enum direction{west=1, northWest=2, north=3}; void LCS_Length(string X, string Y, int** c, direction** b) { int m = X.length() + 1; int n = Y.length() + 1; for(int i = 1; i<m; i++) c[i][0] = 0; for(int j = 0; j<n; j++) c[0][j] = 0; for(int i = 1; i<m; i++) { for(int j = 1; j= c[i][j-1]) { c[i][j] = c[i-1][j]; b[i][j] = north; } else { c[i][j] = c[i][j-1]; b[i][j] = west; } } } } void print_LCS(direction** b, string X, int i, int j) { if(i == 0 || j == 0) return; if(b[i][j] == northWest) { print_LCS(b, X, i-1, j-1); cout<<X[i-1]<<" "; } else if (b[i][j] == north) print_LCS(b, X, i-1, j); else print_LCS(b, X, i, j-1); } #endif
Here is the main file
#include "LCS_Functions.h" int main() { cout<<"This program inputs two strings of characters." <<"nIt then finds the longest common substring that the two strings have in common.n" <<"A substring si any sequence of characters which increase in order"<<endl<<endl; string X, Y; cout<<"Please Enter String X without spaces: "<>X; //clear input stream cin.clear(); cin.ignore(256, 'n'); cout<<"Please Enter String Y without spaces: "<>Y; cin.clear(); cin.ignore(256, 'n'); //declare the arrays int** c (for the string length), direction** b (to keep track of elements in string) int** c; direction** b; c = new int *[X.length() + 1]; b = new direction *[X.length() + 1]; for(int i=0; i<X.length() + 1; i++) { c[i] = new int[Y.length() + 1]; b[i] = new direction[Y.length() + 1]; } LCS_Length(X, Y, c, b); cout<<endl<<"Printing c:"<<endl; for(int i = 0; i < X.length()+1; i++) { for(int j = 0; j<Y.length()+1; j++) cout<<c[i][j]<<" "; cout<<endl; } cout<<endl<<"Printing b"<<endl; for(int i = 0; i < X.length()+1; i++) { for(int j = 0; j<Y.length()+1; j++) cout<<b[i][j]<<" "; cout<<endl; } cout<<"nThe longest common substring is the following:"<<endl; print_LCS(b, X, X.length(), Y.length()); cout<<"nngoodbye"<<endl; return 0; }