// CS454 (2009)
// by Alexandre Lomovtsev

public class LCI{

   public static void main(String[] args) {

      // testing strings:
      String s1=      "AGACTAGTTAC";
      String s2=    "CGAGACGT";


      System.out.println(   "S1:\t"  + s1 +
                          "\nS2:\t"  + s2 +
                          "\nLCI:\t" + findLCI( s1, s2 ) );
   }

   static String findLCI( String s1, String s2 ) {

      if (s1.isEmpty() || s2.isEmpty())
         return "";

      String s = "";
      int m = s1.length();
      int n = s2.length();
      int[][] d = new int[m][n];
      int length = 0;

      for(int i=0; i<m; i++) {
         for(int j=0; j<n; j++) {
            if( (s1.charAt(i)) == (s2.charAt(j)) ) {
               d[i][j] = ( i==0 || j==0 ) ? 1 : d[i-1][j-1] + 1;
               if(d[i][j] > length) {
                  length = d[i][j];
                  s = "";
               }
               if(d[i][j] == length) {
                  s = s1.substring(i-length+1, i+1);
               }
            }
         }
      }
      return s;
   }
}