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