The Longest Common Subsequence

                            Solution in C :

In C++ :





#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void LCS(const vector<int> &A, const vector<int> &B) {
    int n = A.size(), m = B.size();
    vector<int> lens(m+1,0);
    vector<vector<int>> prev(n+1,vector<int>(m+1,0));
    int topleft;
    for(int i = 1; i <= n; i++) {
        topleft = 0;
        for(int j = 1; j <= m; j++) {
            int len;
            if(A[i-1] == B[j-1]) {
                len = topleft+1;
                prev[i][j] = 1; // topleft
            } else {
                if(lens[j] > lens[j-1]) {
                    len = lens[j];
                    prev[i][j] = 2; // top
                } else {
                    len = lens[j-1];
                    prev[i][j] = 3; // left
                }
            }
            topleft = lens[j];
            lens[j] = len;
        }
    }
    // print LCS
    int i = n, j = m, idx = 0;
    vector<int> lcs(lens[m],0);
    while(prev[i][j] != 0) {
        if(prev[i][j] == 1) {
            lcs[idx++] = A[i-1];
            i--;
            j--;
        } else if(prev[i][j] == 2) {
            i--;
        } else {
            j--;
        }
    }
    for(int i = lcs.size()-1; i >= 0; i--) {
        if(i != 0) {
            cout << lcs[i] << ' ';
        } else {
            cout << lcs[0] << endl;
        }
    }
}

int main() {  
    int n, m;
    cin >> n >> m;
    vector<int> A(n), B(m);
    for(int i = 0 ; i < n; i++) {
        cin >> A[i];
    }
    for(int i = 0; i < m; i++) {
        cin >> B[i];
    }
    LCS(A,B);
    return 0;
}








In Java :





import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int sizeM = s.nextInt();
        int sizeN = s.nextInt();
        int[] m = new int[sizeM];
        for (int i = 0; i < sizeM; i++) {
            m[i] = s.nextInt();
        }
        int[] n = new int[sizeN];
        for (int i = 0; i < sizeN; i++) {
            n[i] = s.nextInt();
        }
        System.out.println(LCS(m, n));
    }
    
    private static String LCS(int[] m, int[] n) {
        int[][] table = new int[m.length + 1][n.length + 1];
        for (int i = 1; i < table.length; i++) {
            for (int j = 1; j < table[i].length; j++) {
                if (m[i - 1] == n[j - 1]) table[i][j] = table[i - 1][j - 1] + 1;
                else table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
            }
        }
        StringBuilder sb = new StringBuilder();
        int i = m.length;
        int j = n.length;
        while (i > 0 && j > 0) {
            int s = table[i][j];
            int x = table[i - 1][j - 1];
            int y = table[i - 1][j];
            int z = table[i][j - 1];
            if (s > x && s > y && s > z) { 
                sb.insert(0, " " + m[i - 1]); i--; j--; 
            }
            else if (y > z) i--;
            else j--;
        }
        return sb.deleteCharAt(0).toString();
    }
}








In C :





#include <stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
int lcs[999][999];
int a[999],b[999];
int f;
void backtrack(i,j){
	if(i==0||j==0);
	else if(a[i]==b[j])backtrack(i-1,j-1),f=printf(f?" %d":"%d",a[i]);
	else if(lcs[i][j-1]>lcs[i-1][j])backtrack(i,j-1);
	else backtrack(i-1,j);
}
main(){
  int i,j,_a,_b;
  scanf("%d%d",&_a,&_b);
  for(i=1;i<=_a;i++)scanf("%d",a+i);
  for(i=1;i<=_b;i++)scanf("%d",b+i);
  for(i=1;i<=_a;i++)
    for(j=1;j<=_b;j++)
      lcs[i][j]=max(max(lcs[i-1][j],lcs[i][j-1]),lcs[i-1][j-1]+(a[i]==b[j]));
  backtrack(_a,_b);puts("");
}








In Python3 :





def backtrack(c, x, y, i=None, j=None):
    i = i if i is not None else len(x) - 1
    j = j if j is not None else len(y) - 1
    
    if i < 0 or j < 0:
        return []
    
    if x[i] == y[j]:
        return backtrack(c, x, y, i-1, j-1) + [x[i]]
    
    if c[i][j-1] > c[i-1][j]:
        return backtrack(c, x, y, i, j-1)
    
    return backtrack(c, x, y, i-1, j)

def lcs(x, y):
    c = [[0 for j in range(len(y) + 1)] for i in range(len(x) + 1)]
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i] == y[j]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i][j-1], c[i-1][j])
    return backtrack(c, x, y)
    return c[len(x)-1][len(y)-1]


    
if __name__ == '__main__':
    n, m = map(int, input().split())
    A, B = (list(map(int, input().split())) for i in range(2))
    result = lcs(A, B)
    print(' '.join(map(str, result)))