// This code computes the Longest Common Substring of two strings given as
// command line parameters.
//
// 1. Save this file as LongCommSubstr.java
// 2. Compile it with javac LongCommSubstr.java
// 3. Run with java LongCommSubstr X Y, where X and Y are strings 

public class LongCommSubstr
{
  public static void main(String[] args)
  {
    if (args.length < 2)
    {
      System.out.println("Please provide two strings for processing");
      System.exit(0);
    }
    String X = " " + args[0];   // get strings from the command line
    String Y = " " + args[1];   // the strings start with index 1

    int m = X.length()-1;       // lengths of strings
    int n = Y.length()-1;
    int[][] c = new int[m+1][n+1];// the array is initialized with 0s
    char[][] b = new char[m+1][n+1]; // array that will store '|', '-', and '\'

    LCS(X, Y, c, b);            // filling up the arrays c and b
    // printing the table
      System.out.print("  j|0");
      for (int j=1; j<=n; j++)
        System.out.print("  " + j);
      System.out.print("\ni  |Y");
      for (int j=1; j<=n; j++)  
        System.out.print("  " + Y.charAt(j));
      System.out.print("\n---+");
      for (int j=1; j<=3*n+1; j++) 
        System.out.print("-");
      System.out.print("\n0 X|0");
      for (int j=1; j<=n; j++)
        System.out.print("  0");
      for (int i=1; i<=m; i++)
      {
        System.out.print("\n   |\n" + i + " " + X.charAt(i) + "|0");
        for (int j=1; j<=n; j++)
          System.out.print(" " + b[i][j] + c[i][j]);
      }
      System.out.println("\n"); 

      System.out.print("LCS(\"" + X.substring(1, X.length()) + "\", \"" + 
           Y.substring(1, Y.length()) + "\") = \"");
      Print_LCS(b, X, m, n);
      System.out.println("\""); 
  }

  public static void LCS(String X, String Y, int[][] c, char[][] b)
  {
    int m = X.length()-1;
    int n = Y.length()-1;
    for (int i=1; i<=m; i++)
    for (int j=1; j<=n; j++)
      if (X.charAt(i) == Y.charAt(j))
      {
        c[i][j] = c[i-1][j-1] + 1;
        b[i][j] = '\\';
      }
      else if (c[i-1][j] >= c[i][j-1])
      {
        c[i][j] = c[i-1][j];
        b[i][j] = '|';
      }
      else
      {
        c[i][j] = c[i][j-1];
        b[i][j] = '-';
      }
  }

  public static void Print_LCS(char[][] b, String X, int i, int j)
  {
    if (i==0 || j==0) return;

    if (b[i][j] == '\\')
    {
      Print_LCS(b, X, i-1, j-1); 
      System.out.print(X.charAt(i));
    }
    else if (b[i][j] == '|')
      Print_LCS(b, X, i-1, j);
    else
      Print_LCS(b, X, i, j-1);
  }
}