Longest Common Subsequence in C++

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&lt;m; i++)
		c[i][0] = 0;
	for(int j = 0; j&lt;n; j++)
		c[0][j] = 0;
 
	for(int i = 1; i&lt;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&lt;&lt;X[i-1]&lt;&lt;&quot; &quot;;
	}
	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;
}