CareerCup

Put the first string into a suffix tree of words and then find common substring and the same for the other file. But I don't how the hell to create a suffix tree and to find a substring

http://en.wikipedia.org/wiki/Longest_common_substring_problem

my code in java:
public class LCSS {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String s1 = "It is snowing and I want to drive home.";
String s2 = "It is snowing and I want to go skiing.";
String s3 = "It is hot and I want to go swimming.";
String len = find_lcss(s1, s2);
len = find_lcss(len, s3);
//System.out.println("The length of longest: " + len);
System.out.println(s1.replace(len, " "));
System.out.println(s2.replace(len, " "));
System.out.println(s3.replace(len, " "));

}

/**
* @param s1
* @param s2
* @return
*/
public static String find_lcss(String s1, String s2){
if(s1.isEmpty() || s2.isEmpty())
return "";
int [][] table = new int[s1.length()][s2.length()];
int maxLen = 0;
int end_index = 0;

for(int i=0; i<s1.length();i++)
{
for(int j=0;j<s2.length();j++)
{
if(s1.charAt(i)!=s2.charAt(j))
{
table[i][j] = 0;
}
else
{
if(i==0 || j==0)
{
table[i][j] = 1;
}
else
{
table[i][j] = table[i-1][j-1] + 1;
}
}
if(maxLen < table[i][j])
{
maxLen = table[i][j];
end_index = i;
}
}
}
StringBuilder res = new StringBuilder();
for(int i =end_index+1-maxLen; i<end_index+1; i++){
res.append(s1.charAt(i));
}
return res.toString();
//System.out.println(end_index);
}
}

create common suffix tree for all the files and each leave contains the info about which all file has that suffix.

check for the sentence with more than 3 word and which is longest and contains all the files info at its leave
(dont forget to store the position along with file at the leave)

How about this?
***********
i=1;
Nextword = firstWord;
do
{
pattern = file1;
do{
for(i=0;i<n;i++)
{
if(checkIfPatternInFile (pattern , file2)!=0)
break ;
}

if(i==n)
{
printf("common string is file1");
found = true;
break;
}
else
{
pattern = RemoveWordFromPattern(pattern, Nextword);
}
while(found == false && file1 has more than 3 words);

i++;
Nextword = LastWord;
}while(found == false && i<=3);
***********
Of course, i have not defined the functions, checkIfPatternInFile() and RemoveWordFromPattern(). But that should be relatively simple.

why "It is" is not removed?

"It is" is not removed because the fragment to be removed should be atleast 3 words . "It" " is" are only two words.

"It is" is not removed because the fragment to be removed should be atleast 3 words . "It" " is" are only two words.

"It is" is not removed because the fragment to be removed should be atleast 3 words . "It" " is" are only two words.

I think they are expecting 'diff' and text replace in file.. for this question..

may be you're right ! need to ask amazon guys, though !