Finding the length of the longest common substring from two given strings in Java

Question

The following code returns the length of longest common substring from given two strings in Java. For cases of around \10ドル^6\$ characters, it is still not fast enough to get the answer in a few seconds.

Any suggestions for efficiency will be greatly appreciated!

int longestCommonSubstring(String s, String t){ 
 int maxlength = 0;
 for(int i=0; i<s.length(); i++){
 for(int j=0; j<t.length(); j++){
 int count = 0;
 int g = 0;
 while(i+g<s.length() && j+g<t.length()){
 if(t.charAt(j+g)==s.charAt(i+g)){
 count++;
 maxlength = Integer.max(count, maxlength);
 }
 else{
 count = 0; 
 }
 g++;
 }
 }
 }
 return maxlength;
}

• Mast: Is this the solution to a programming-challenge perhaps?
• Sanjiv: @Mast Yes it is

Answer 1

Stylistic review

You really need some whitespace here and there. Please put a space between operators and between keywords / brackets, etc. For example:

 for(int i=0; i<s.length(); i++){
 for(int j=0; j<t.length(); j++){

This would be more readable:

 for (int i = 0; i < s.length(); i++) {
 for (int j = 0; j < t.length(); j++) {

You also could use better variable names. s and t aren't very obvious, and neither is g.

Overall, the code could potentially be more readable if it could be restructured into using some of the Stream algorithms, but that's not an easy task.

Performance review

The easiest solutions to this problem take \$O(nm)\$ time, where \$n\$ and \$m\$ are the lengths of the 2 input strings. Your algorithm is slower than this. Here are some places that slow it down:

• You keep incrementing g even once the strings become dissimilar. You want to break out of the while loop once t.charAt(j + g) != s.charAt(i + g). Because we keep incrementing i and j, you don't have to worry about missing later common substrings.
• If s = "abcdefg" and t = "abcdefg", one iteration of the inner for loop will find the correct maxLength. However, you then increment j and have to iterate over bcdefg again with the inner while loop even though we know that bcdefg is a shorter substring than abcdefg. You can keep your count variable from the inner while and use that to skip forward in j, at the very least.
• This isn't an algorithmic concern, but you compute Integer.max on every single char, but you only need to do it once you find a complete substring. This can be accomplished by moving that line into the else block (before the count = 0, which can be removed if you follow my first point).

Those are the easy performance improvements I can see. If you still need to speed up your code, the easiest thing to do would probably be to redesign your algorithm.

---

One of the more powerful techniques in algorithm design is known as dynamic programming. It is basically just breaking down the problem into smaller pieces, then combining it together. For example, if it was possible to find the largest common substring (LCS) of the left and right halves of s and t, then use that information to find the LCS of the whole thing, that would be solving the problem through dynamic programming.

Wikipedia helpfully has a page on this problem. For a dynamic programming solution, it shows that you can solve this by taking all the possible prefixes of the strings, and finding the longest common suffixes for each pair of possible prefixes. If that algorithm isn't efficient enough, it helpfully provides another one which is faster.

• Sanjiv: Thanks for the input. I really appreciate it. I want to clarify what I am actually trying to do. When you say I need to break out of the loop once I find two characters are unequal, it does miss possible common strings. For instance, in "jumper" & "romper", if I skip because the initials 'j' & 'r' are not equal, then I miss the matching sequence "mper". I would be moving onto comparing 'j' & the second letter 'o'. The i and j are there to determine where the comparison starts for each string, and g does the increment of the position of comparison.