Java - нахождение самой длинной подстроки - проблема LinkedList

Question

Я получил задачу реализовать алгоритм, который найдет максимально длинную подстроку из двух заданных строк:

Введите:

String s1="AAABBA";
String s2="ABAABBAAA";

так что это будет AABBA. Итак, я реализовал метод, который возвращает строку, но потом он меня понял - что, если есть две подстроки с одинаковой, максимально возможной длиной? Тогда я решил использовать LinkedList.

например:

String s1="ABCIJK";
String s2="ABCDEFGHIJK";

Итак, я ожидаю, что здесь на самом деле две подстроки - это ABC и IJK соответственно.

У меня есть код:

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));

    } 
}   

И он возвращает мне только «IJK» вместо [ABC, IJK]. когда я комментирую

allFound.remove (theLongest)

в случае [ABC, IJK] работает нормально, но затем добавляет [AAA] к результату [AABBA], что не ожидается. Есть ли способ изменить условие, чтобы оно добавляло в список только самые длинные строки? или удалить все предыдущие, более короткие строки?

Заранее спасибо

Answer 1

Я соответственно изменил метод, пожалуйста, проверьте мой встроенный комментарий

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)))
                {
                    theLongest = s1.substring(j, j+i);
                    // before adding any string check the length of existing string if it is less then remove it
                    if (allFound.size() > 0 && allFound.getFirst().length() < theLongest.length()) {
                        allFound.removeFirst();
                    }
                    allFound.add(theLongest);
                }
            }
        }

        return allFound;
    }