public class LCI {

	
	public static void main(String[] args) {
		// testing strings:
	     // String s1=      "AGACTAGTTAC";
	      //String s2=    "CGAGACGT";
	      
		String s1= "FTFTALLLAVAV";
		String s2="FTAVLLAAV";

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

	}
	
	private static String findLCI(String s1, String s2){
		int maxLen = 0;
		String ls, ss;
		if(s1.length()>s2.length()){
			maxLen = s2.length();
			ls = s1;
			ss = s2;
		}	
		else {
			maxLen = s1.length();
			ls = s2;
			ss = s1;
		}
		if(maxLen == 0) return "";
		String lci = "";
		for(int i = 0; i < maxLen; i++){
			String tempS;
			boolean isFound = false;
			for(int j = 0; j <= i; j++){
				tempS = ss.substring(j, maxLen-i+j);
				if(ls.contains(tempS)){
					isFound = true;
					lci = tempS;
					break;
				}
			}
			if(isFound == true)
				break;
		}
		return lci;
	}

}