lcs_trace.cpp

void trace(int i, int j) {
	if (i == n || j == m) return ;
 
	int ans = go(i, j);
 
	int c1 = 0;
	if (s[i] == t[j]) {
		c1 = 1 + go(i + 1, j + 1);
		if (c1 == ans) {
			cout << s[i];
			trace(i + 1, j + 1);
			return;
		}
	}
	int c2 = 0 + go(i + 1, j);
	if (c2 == ans) {
		trace(i + 1, j);
		return;
	}
	int c3 = 0 + go(i, j + 1);
	if (c3 == ans) {
		trace(i, j + 1);
		return;
	}
}
// call trace(0, 0)