Algorithms for Coding Interviews in C++/

...

/

Solution: Longest Common Substring

Solution: Longest Common Substring

This review provides a detailed analysis of the different ways to solve the Longest Common Substring problem

We'll cover the following...

Solution #1: Brute Force

Press + to interact
#include <iostream>
#include <string>
using namespace std;
int longestCommonSubstrLengthRec(string s1, string s2, int i1, int i2, int count) {
  if (i1 == s1.length() || i2 == s2.length())
    return count;
  if (s1[i1] == s2[i2])
    count = longestCommonSubstrLengthRec(s1, s2, i1 + 1, i2 + 1, count + 1);
  int c1 = longestCommonSubstrLengthRec(s1, s2, i1, i2 + 1, 0);
  int c2 = longestCommonSubstrLengthRec(s1, s2, i1 + 1, i2, 0);
  return max(count, max(c1, c2));
}
int longestCommonSubstrLength(string s1, string s2) {
  return longestCommonSubstrLengthRec(s1, s2, 0, 0, 0);
}
int main() {
  string S1 = "www.educative.io/explore";
  string S2 = "educative.io/edpresso";
  string s1 = "0abc321";
  string s2 = "123abcdef";
  cout << longestCommonSubstrLength("abc", "zabcdeui") << endl;
  //cout << longestCommonSubstrLength(S1, S2) << endl;
}

This solution finds all the substrings of the two given strings, and discovers the longest common substrings between the two.

Pseudocode

If the strings have a matching character, we can recursively check for the remaining length of each and keep a track of the current matching length.
If the strings don’t match, start two new recursive calls by skipping one character from each string.

The length of the longest common substring will be the maximum number returned by the three recursive calls in the two options above.

Time Complexity

The time complexity of this code is exponential: O(2m+n)O(2^{m+n}).

Notice that the time complexity is so high that the function times out before it can process the longer inputs S1 and S2. Try uncommenting the call.

The space complexity is O ...