I got a task to implement algorithm that will find the longest possible substring from two given strings:
Input:
String s1="AAABBA";
String s2="ABAABBAAA";
so for that it would be AABBA. So i've implemented a method which returns a String, but then it got me - what if there are two substrings with equal, maximum possible length? That's when I decided to use LinkedList instead.
for example:
String s1="ABCIJK";
String s2="ABCDEFGHIJK";
So i am expecting here two substrings actually that are ABC and IJK respectively.
i've got the code:
import java.util.LinkedList;
public class SubstringFinder {
public static LinkedList<String> findTheLongestSubstring(String s1, String s2)
{
LinkedList<String> allFound = new LinkedList<String>();
String theLongest="";
if(s1.length()>s2.length())
{
s1 = s1 + s2;
s2 = s1.substring(0, (s1.length() - s2.length()));
s1 = s1.substring(s2.length());
}
for(int j=0;j<s1.length();j++)
{
for(int i=s1.length()-j; i>=0;i--)
{
if(s1.substring(j,j+i).length()>=theLongest.length() && s2.contains(s1.substring(j,j+i)))
{
allFound.remove(theLongest);
theLongest=s1.substring(j,j+i);
allFound.add(theLongest);
}
}
}
return allFound;
}
public static void main(String[] args) {
//String s1="ABCIJK";
//String s2="ABCDEFGHIJK";
String s1="AAABBA";
String s2="ABAABBAAA";
System.out.println(findTheLongestSubstring(s1,s2));
}
}
And it returns me only "IJK" instead of [ABC, IJK]. when I comment
allFound.remove(theLongest)
it works OK in case of [ABC, IJK] but then it also adds [AAA] to the [AABBA] result, which is not expected. Is there any way to modify the condition so it adds only the longest strings to the list? or to remove all of the previous, shorter strings?
Thanks in advance