Fix for LCS code

lcs-fix.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long int llint;
typedef long int ullint;

const long long int MAX_STRING_SIZE_A = 1000;
const long long int MAX_STRING_SIZE_B = 1000;

llint arr[MAX_STRING_SIZE_A][MAX_STRING_SIZE_B];
inline llint max_col(llint col_id, llint row_count)
{
    llint max = -1;
    for (llint i = 0 ; i <= row_count ; i++) max = ((max > arr[i][col_id]) ? max : arr[i][col_id]);
    return max;
}

inline llint max_row(llint row_id, llint col_count)
{
    llint max = -1;
    for (llint i = 0 ; i <= col_count ; i++) max = ((max > arr[row_id][i]) ? max : arr[row_id][i]);
    return max;
}

inline void purge(std::string &str1, std::string &str2, llint anchor)
{
    // cout << "purge invoked\n";
    while (max_row(str1.length() - 1, str2.length()) != anchor) str1.pop_back();
    while (max_col(str2.length() - 1, str1.length()) != anchor) str2.pop_back();
}

std::string lcs (std::string str1, std::string str2)
{
	str1 = " " + str1; str2 = " " + str2;
	
	for (llint i = 1 ; i <= str1.length() - 1 ; i++)
	for (llint n = 1 ; n <= str2.length() - 1 ; n++)
	{
		if (str1[i] == str2[n]) arr[i][n] = arr[i - 1][n - 1] + 1;
		else arr[i][n] = (arr[i - 1][n] > arr[n - 1][i]) ? arr[i - 1][n] : arr[n - 1][i];
	};
	//std::cout << "Length of the longest common subsequence : " << arr[str1.length() - 1][str2.length() - 1] << std::endl;
	
    llint max = 0;
    for (llint i = 1 ; i <= str1.length() - 1 ; i++)
	for (llint n = 1 ; n <= str2.length() - 1 ; n++)
    max = ((arr[i][n] > max) ? arr[i][n] : max);
    // cout << max;

    purge(str1, str2, max);
    llint i = str1.length() - 1, n = str2.length() - 1;

	std::string out = "";
    
	while (i >= 1 && n >= 1)
	{
		if (str1[i] == str2[n])
		{
			out.push_back(str1[i]);
			i--; n--;
		}
		else if (arr[i - 1][n] > arr[i][n - 1])
		{
			i--;
		}
		else n--;
	}
	std::reverse(out.begin(), out.end());
	return out;
}