LCS dynamic

mail@pastecode.io avatar
unknown
c_cpp
3 years ago
611 B
5
Indexable
Never
int solve2(std::string x, std::string y, int lengthX, int lengthY)
{
	int** L = new int*[lengthX+1];
	for (int i = 0; i < lengthX + 1; i++)
		L[i] = new int[lengthY + 1];

	for (int i = 0; i <= lengthX; i++)
	{
		for (int j = 0; j <= lengthY; j++)
		{
			if (i == 0 || j == 0)
				L[i][j] = 0;

			else if (x[i - 1] == y[j - 1])
			{
				L[i][j] == L[i - 1][j - 1] + 1;
			}

			else
				L[i][j] = std::max(L[i - 1][j], L[i][j - 1]);
			
		}
	}
	
	return L[lengthX][lengthY];
}

	int main()
	{
	    std::cout << "The length is : " << solve2(x, y, x.length(), y.length());
	    
	}