java - 寻找最长公共(public)子串java的高效循环程序

Question

我使用 jersey API 检索了 200 条推文。我想找到两条具有 longest common substring 的推文。这就是我所拥有的。 tweetList 是 Tweet 对象的 ArrayList。 comapreTweets 方法比较推文对象的最长子字符串。

Tweet t1=new Tweet();Tweet t2=new Tweet();
    int longestString=0;

    for(int i=0;i<tweetList.size();i++)
    {int store=0;Tweet comparer=null;
        for(int j=i+1;j<tweetList.size();j++)
        {
            if(j!=i){
            int result=tweetList.get(i).compareTweets(tweetList.get(j));
            if(result>store){
                store=result;
                comparer=tweetList.get(j);
            }}
        }
        if(longestString<store)
        {
            longestString=store;
            t1=tweetList.get(i); t2=comparer;
        }
}

如果我检索 200 条推文，那么这将循环大约。 40000次。我需要一种更有效的方法。

编辑该循环还以相反的顺序比较相同的推文假设我的 tweetList 包含 {a,b,c,d} ；当i=1 和j=3 时比较在b 和d 之间；当 i=3 和 j=1 时，比较是 d & b。如何避免这种情况。

SOLUTION 而不是 j=0 它应该是 j=i+1。它循环 19701 次。

Answer 1

199 + 198 + ... + 1 = 19900

我相信 19900 次 是一个明智的答案。循环中将近一半的比较是多余的。您只需将第一条与其余 199 条推文进行比较，将第二条与其余 198 条推文进行比较，依此类推。进一步优化优于 19900 次是可能的，但我想不出一个。