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.
Imagine you have three strings:
We generate all suffixes of every string. Every suffix of the first string is:
For the second we have:
And finally for the third:
If we sort all suffixes for all strings, we get the following sorted set:
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
We go to the next pair from different strings, which is
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.