/**LongestCommonSubstring.java * given multiple words, we need to find the longest string * that is a substring of all words * ************ * input format: a string words, separated by spaces that * can also contain numbers * ************* * output format: * a string representing the longest common substring, if there are * multiple longest common substrings, output the smallest one * in alphabetical order */ import java.util.*; public class Program { // this list contains the common substring of the smallest word //in the line and another word private static List commonWordOne=new ArrayList(); //list contains the common substring of all words private static List commonWordSecond=new ArrayList(); private static List commonWordFinal=new ArrayList(); /********************************************************************** * the approach: * 1-get the smallest word of all the words * 2-find the characters that are common between him and another word * 3-test for common substring between the two words * 4-find out the words of "commonWordOne" that are also common * for all the words in the line * 5- check for multiple common words * */ public static void main(String[] args) { String line[]=readInput(); int indexOfSmallest= smallest(line); testingForCommonCharacter(line,indexOfSmallest); sortingBySize(); compareTheLongest(line); eliminateTheRep(); multipleSubstringCheak(); Collections.sort(commonWordSecond); System.out.println(commonWordSecond.get(0)); } /***********************************************************************/ private static void multipleSubstringCheak() { for(int i=1;icommonWordSecond.get(i).length()) { commonWordSecond.remove(i); } } } /*********************************************************************** * eliminate the substring that already exist in larger ones * */ private static void eliminateTheRep() { for(int i=0;i=0;i--) { test=0; for(int j=0;j stringLengthComparator = new Comparator() { @Override public int compare(String o1, String o2) { return Integer.compare(o1.length(), o2.length()); } }; /********************************************************************** * sorting the words from the smallest to the longest*/ private static void sortingBySize() { Collections.sort(commonWordOne,stringLengthComparator); } /*************************smallest*word*of*the*line********************* * find out the smallest word of all the line of words * and return it's index * */ private static int smallest(String line []) { int ReferenceSize=line[0].length(); int indexOfSmallest=0; for(int i=1;i1;i--) { String strOneShaped=strInTest.substring(0, i);//test the first word and every time take off one char from the end for(int j=strIntestTwo.length();j>1;--j) { String strTwoShaped=strIntestTwo.substring(0,j);// from the similar char to same size of the first one in test if(strOneShaped.equalsIgnoreCase(strTwoShaped)) {//there equal and have 2 or more characters commonWordOne.add(strOneShaped); } } } } /***************Read*the*Input*String*line***********/ private static String[] readInput() { Scanner scan=new Scanner(System.in); String line[]=scan.nextLine().split(" "); return line; } /******************************************* ********/ }