# Finding the longest common substring between two tweets

I retrieved 200 tweets using the Jersey API. I want to find two tweets which have the longest common substring.

tweetList is an ArrayList of Tweet objects. The comapreTweets method compares tweet objects for longest substring.

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


If I retrieve 200 tweets then this will loop approx. 40000 times. I require a more efficient way.

• I don't know what's going on inside of the loop, but do strings need to be compared to each other twice? For example, i=5, j=3 and i=5, j=3 will compare tweets 5 and 3 twice. This would be a fairly minor improvement, but if it can be done (and it probably can be), it only takes about 10 characters of changes. (Also, size shouldn't be called over and over again) Dec 1 '12 at 4:08
• @Corbin but I did include if(j!=i) to ensure that. Can you point where will this repetition occur in my code Dec 1 '12 at 4:25
• You've made sure not to compare a tweet to itself, but the comparison is two sided. Assume you have tweetList = {a, b, c, d}. This means i and j will both run from 0 to 3. Imagine when i = 1 and j = 3. Simple enough situation: compare(b, d). Now imagine when i = 3 and j = 1: compare(d, b). It's the same comparison, just inverted order. Dec 1 '12 at 4:32
• @Corbin do you know any way to prevent it Dec 1 '12 at 4:49
• Simple: for (i = 0; i < n; ++i) { for (j = i + 1; j < n; ++j) {} } (Note that this is still quadratic. It will just loop (n^2)/2 + n/2 times instead of n^2. So for 200 tweets, it would run 20100 times versus 40000.) Dec 1 '12 at 5:12

The classic solution to this well-known problem is using a Suffix array (see also Suffix tree and Generalized Suffix tree which is a more general data structure for these kinds of problems.). Basically, a Suffix array is a sorted set in which every suffix of every tweet is inserted. By using the prefixes of those sorted suffixes, you can find the longest common substring by iterating through every pair of substrings from different tweets in the Suffix array.

Construction of all suffixes can be performed in O(140 k) time, where k is the the amount of tweets, and 140 is the length of a tweet. These can then be sorted in O(k * log(k)) time. Finally allowing you to find the longest common substring in O(k 140) time. Which results in roughly 57 800 operations.

The algorithm proposed in your orignal post loops through every tweet twice, and has to, worst case, compare all the characters. This leaves a total complexity of O(k^2 * 140) which is 5 600 000 operations.

## Example

Imagine you have three strings:

1. ababa
2. bataba
3. dafjkl

We generate all suffixes of every string. Every suffix of the first string is:

• ababa
• baba
• aba
• ba
• a

For the second we have:

• batabak
• atabak
• tabak
• abak
• bak
• ak
• a

And finally for the third:

• dafjkl
• afjkl
• fjkl
• jkl
• kl
• l

If we sort all suffixes for all strings, we get the following sorted set:

• a
• a
• aba
• ababa
• abak
• afjkl
• ak
• atabak
• ba
• baba
• bak
• batabak
• dafjkl
• fjkl
• jkl
• kl
• l
• tabak

Thus we iterate through every pair of suffixes for different strings, to find the longest common prefix in suffixes from two different strings. This is equal to the longest common substring.

First encounter is a (origining from the 1st string) and a (2nd string), thus our longest common substring (LCS) is of length 1 and equal to a.

We go to the next pair from different strings, which is aba/ababa and abak, both of length 3. This is set as the LCS so far. If you keep going through the set using this algorithm, you will find that this is the LCS for these three strings.

I do not know Java, however, I just created a C++ solution to a very similar problem. The solution for your problem is essentially the same, you just have to generate substrings for k strings rather than two.

• You said "Imagine you have four strings:" but don't you mean 3? If not, what is the fourth? Mar 6 '14 at 20:58