Shortest length common supersequence.cpp

/*
///////////////////////////////////////////
//Question/Info

Shortest Common Supersequence Length

Given two strings str1 and str2,
the task is to find the length of the
shortest string that has both str1 and str2 as subsequences.

Examples :

Input:   str1 = "geek",  str2 = "eke"
Output: 5
Explanation:
String "geeke" has both string "geek"
and "eke" as subsequences.

Input:   str1 = "AGGTAB",  str2 = "GXTXAYB"
Output:  9
Explanation:
String "AGXGTXAYB" has both string
"AGGTAB" and "GXTXAYB" as subsequences.

///////////////////////////////////////////
*/

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

#define int 		   long long int
#define setbits(x) 	   __builtin_popcount(x)
#define pb(x) 		   push_back(x)
#define mp(x,y) 	   make_pair(x,y)
#define eb(x) 		   emplace_back(x)
#define ct(x) 		   cout<<x<<endl;
#define ct2(x,y) 	   cout<<x<<" "<<y<<endl;
#define forn(i,n) 	   for(int i = 0; i < (int)(n); i++)
#define forx(i,x,n)    for(int i = x; i < (int)(n); i++)
#define all(v) 		   v.begin(),v.end()
#define fsp(x,y)       fixed<<setprecision(y)<<x;
#define PI 			   3.1415926535897932384626433832795
#define MOD 		   1000000007 // (1e9+7)
#define pii 		   pair<int,int>
#define pis 		   pair<int,string>
#define vi  		   vector<int>
#define vii 		   vector<pii>
#define mii 		   map<int,int>

// typedef long long int lli;
typedef long double ld;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

void c_p_c()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

// using bottom up dp
int scs(string a, string b, int la, int lb) {


	int dp[la + 1][lb + 1];
	forn(i, la + 1) {
		forn(j, lb + 1) {
			// base case
			if (i == 0 or j == 0) {
				dp[i][j] = 0;
			}

			else {
				if (a[i - 1] == b[j - 1]) {
					dp[i][j] = 1 + dp[i - 1][j - 1];
				}

				else {
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
				}

			}
		}
	}

	/*

	So now we can get the dp length...
	So now considering the strings: "geek" & "eke".
	So the common strings would be: ek, and this subsequence is
	repeated in both. Hence if we have to find a supersequence:
	The easiest supersequence we can have is : "geekeke"
	As it has both strings. But this is a long supersequence.
	We have to find an optimised supersequence. Since we have "ek",
	repeating twice in both, we can remove one of the "ek" and hence
	our supersequence would be optimised, i.e: "geeke".
	Since our focus is only on length, hence the length of the
	optimised supersequence would be : la+lb-(dp[la][lb])

	*/

	int kk = la + lb - dp[la][lb];

	return kk;
}

int32_t main() {

///////////
	c_p_c();
///////////

	// code

	/*
	int t ; cin >> t; while(t--){}
	*/

	string a = "geek";
	string b = "eke";

	int la = a.length();
	int lb = b.length();


	// dp bottom up
	ct(scs(a , b , la, lb));


// cerr << "time: " << clock() << " ms" << '\n';
	return 0;
}