//package ProgrammazioneDinamica;
import java.io.*;

/**
 * Title:        Programmazione Dinamica
 * Description:  Semplici esempi di programmazione dinamica
 * Copyright:    Copyright (c) 2000
 * Company:      Università degli Studi di Verona
 * @author Roberto Posenato
 * @version 1.0
 */

public class MaxSSC {

  public MaxSSC() {
  }


  public static int[][] maxLunghezza(String x, String y) {
    int m = x.length()+1;  //la prima riga deve essere di 0 per supporto
    int n = y.length()+1;  // la prima colonna deve essere 0 per supporto
    int[][] c = new int[m][n];

    for (int i = 1; ( i < m ); i++) {
      for (int j = 1; ( j < n ); j++) {
        if ( x.charAt(i-1) == y.charAt(j-1) ) { //indice stringa inizia a 0
          c[i][j] = c[i-1][j-1] + 1;
        } else {
          if ( c[i-1][j] >= c[i][j-1] )
            c[i][j] = c[i-1][j];
          else
            c[i][j] = c[i][j-1];
        }
      }
    }
    /* In c[m-1][n-1] c'è la lunghezza della sottostringa comune massima
    Infine ricostruisco la sottostringa z ispezionando la matrice c*/
    return c;
  }


  public static String maxSSC(String x, String y) {
    int m = x.length();
    int n = y.length();

    //c è la matrice che contiene le lunghezze dei risultati parziali dei sottoproblemi
    int c[][] = maxLunghezza(x,y);

    // In c[m][n] c'è la lunghezza della massima sottosequenza comune

    int l = c[m][n];

    //inizializzo una stringa vuota con l caratteri
    StringBuffer z = new StringBuffer(l);

    z.setLength(l);

    l--; //ora l rappresenta la posizione corrente della sotto sequenza max

    // n e m invece rappresentano la posizione della soluzione del sottoproblema
    // per le stringhe x[0..m-1] e y[0..n-1]
    while (m > 0 && n > 0) {
      if ( x.charAt(m - 1) == y.charAt(n - 1) ) {
        z.setCharAt(l--, x.charAt(--m));
        n--;
      } else
      if (c[m - 1][n] >= c[m][n - 1])
        m--;
      else
        n--;
    }
    return z.toString();
  }



  public static void main(String args[]) {

    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    String x = null, y = null;

    try {
      System.out.print("Inserire stringa X: ");
      x = input.readLine();
      System.out.print("Inserire stringa Y: ");
      y = input.readLine();
    } catch (IOException e) {};

    System.out.println("String X: " + x);
    System.out.println("String Y: " + y);
    System.out.println("Sotto sequenza massima è: " + maxSSC(x,y));
  }



}