1.

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11 
 * Problem: 10405 - Longest Common Subsequence 
 * Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1346
 * 
 * @author Manuel Hager
 * @version 1.0, 12/01/2010
 * 
 * Method : Ad-Hoc
 * Status : Accepted
 * Runtime: 0.016
 */

#include <iostream>
#include <string>

using namespace std;

#define QUANTITY 1000

char line1[QUANTITY];
char line2[QUANTITY];
int strLen1 = 0;
int strLen2 = 0;

int LCS() {
	strLen1 = strlen(line1);
	strLen2 = strlen(line2);
	
	int c[strLen1 +1][strLen2 +1];
	for(int i = 0; i <= strLen1; i++) {
		c[i][0] = 0;
	}
	for(int j = 0; j <= strLen2; j++) {
		c[0][j] = 0;
	}
	
	for(int i = 1; i <= strLen1; i++) {
		for(int j = 1; j <= strLen2; j++) {
			if(line1[i - 1] == line2[j - 1]) {
				c[i][j] = c[i -1][j -1] + 1;
			}
			else {
				c[i][j] = max(c[i][j -1], c[i -1][j]);
			}
		}
	}
	
	return c[strLen1][strLen2];
}

int main(int argc, char* argv[])
{
	if(!cin.getline (line1,QUANTITY))
		return 0;
	
	do
	{
		cin.getline(line2, QUANTITY);
		cout << LCS() << endl;

	}while(cin.getline(line1, QUANTITY));
	 
	return 0;
}


2. 

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10 
 * Problem: 10405 - Longest Common Subsequence
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1346
 * 
 * @author Evgeni Pavlidis 
 * @version 1.0, 06/02/2010
 * 
 * Method : DP - LCS
 * Status : Accepted
 * Runtime: 0.144
 */

import java.util.*;
import java.io.*;

class Main {
    
    public static void main(String...args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String a, b;

        while( (a = reader.readLine()) != null)
        {
            b = reader.readLine();
            int n,m;
            n = a.length();
            m = b.length();

            int[][] lcs = new int[n+1][m+1];

            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++)
                    if(a.charAt(i-1) == b.charAt(j-1))
                        lcs[i][j] = lcs[i-1][j-1]+1;
                    else
                        lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);

            System.out.println(lcs[n][m]);
        }
    }
}

3.

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
 * Problem: 10405 Longest Common Subsequence
 *
 * @author Robert Reichart
 *
 * Status : Accepted
 * Runtime: 0.300
 */

import java.util.*;

class Main
{
    static int MAX = 1000;
    static char[] X;
    static char[] Y;
    static int i,j,m,n;
    static int[][] c= new int[MAX][MAX];
    static int[][] b = new int[MAX][MAX];

    public static void main(String... args)
    {
        Scanner in = new Scanner(System.in);
        while(in.hasNext())
        {
            //Die beiden Strings einlesen
            String line1;
            line1 = in.nextLine();
            while(line1.equals(""))
            {
                line1=in.nextLine();
            }

            String line2;
            line2 = in.nextLine();
            while(line2.equals(""))
            {
                line2=in.nextLine();
            }

            //Eigentliche Berechnung
            X=line1.toCharArray();
            Y=line2.toCharArray();

            //System.out.printf("LCS length -> %d\n",LCSlength()); /* count length */
            System.out.println(LCSlength());
            //printLCS(m,n); /* reconstruct LCS */
            //System.out.printf("\n");
        }
    }

    static int LCSlength()
    {
        m=X.length;
        n=Y.length;

        for (i=1;i<=m;i++){c[i][0]=0;}
        for (j=0;j<=n;j++){c[0][j]=0;}

        for (i=1;i<=m;i++){
            for (j=1;j<=n;j++) {
              if (X[i-1]==Y[j-1]) {
                c[i][j]=c[i-1][j-1]+1;
                b[i][j]=1; /* from north west */
              }
              else if (c[i-1][j]>=c[i][j-1]) {
                c[i][j]=c[i-1][j];
                b[i][j]=2; /* from north */
              }
              else {
                c[i][j]=c[i][j-1];
                b[i][j]=3; /* from west */
              }
            }
        }

        return c[m][n];
    }

    static void printLCS(int i,int j) {
      if (i==0 || j==0) {return;}

      if (b[i][j]==1) {
        printLCS(i-1,j-1);
        System.out.printf("%c",X[i-1]);
      }
      else if (b[i][j]==2){
        printLCS(i-1,j);
      }
      else{
        printLCS(i,j-1);
      }
}
}

4.

package acm_10405_longest_common_subsequence;

import java.util.Arrays;
import java.util.Scanner;

/**
 * FWP, AusgewŠhlte Probleme aus dem ACM Programming Contest, SS10 
 * Problem: acm_10405_longest_common_subsequence
 * Link: 
 * 
 * @author Martin Lambeck
 * @version 1.0, 08.09.2010
 * 
 * Method : dp
 * Status : Accepted
 * Runtime: 0.348
 */


public class Main
{
	static Scanner sc = new Scanner(System.in);

	static String s1;
	static String s2;
	
	static int[][] memo;
	
	public static void main(String... args)
	{
		while (sc.hasNextLine())
			testcase();
	}

	public static void testcase()
	{
		s1 = sc.nextLine();
		s2 = sc.nextLine();

		memo = new int[s1.length()][s2.length()];
		
		for (int i = 0; i < s1.length(); i++)
		{
			Arrays.fill(memo[i], -1);
		}
		
		int res = lcs(0, 0);

		System.out.println(res);
	}

	static int lcs(int o1, int o2)
	{
		if ((o1 >= s1.length()) || (o2 >= s2.length()))
			return 0;

		if (memo[o1][o2] == -1)
		{
			if (s1.charAt(o1) != s2.charAt(o2))
				memo[o1][o2] = Math.max(lcs(o1+1, o2), lcs(o1, o2+1));
			else
				memo[o1][o2] = lcs(o1+1, o2+1) + 1;
		}
		
		return memo[o1][o2];
	}
}