C/C++ Implementation for Longest Common Substring Algorithm

The longest common substring problem is to find the longest string that is a substring of two or more given strings.

You can build a generalized suffix tree for a set of strings with multiple strings using this implementation. A suffix tree contains all the suffixes of the given text as their keys and positions in the text as their values.

string longestCommonSubstring(const string& str1, const string& str2)
{

  if(str1.empty() || str2.empty())
  {
    return 0;
  }
 
  int *curr = new int [str2.size()];
  int *prev = new int [str2.size()];
  int *swap = NULL;
  int maxSubstr = 0;
   string longest;
 
  for(unsigned int i = 0; i < str1.size(); ++i)
  {
    for(unsigned int j = 0; j < str2.size(); ++j)
    {
      if(str1[i] != str2[j])
      {
        curr[j] = 0;
      }
      else
      {
        if(i == 0 || j == 0)
        {
          curr[j] = 1;
        }
        else
        {
          curr[j] = 1 + prev[j-1];
        }

          if(maxSubstr < curr[j])
        {
          maxSubstr = curr[j];
             longest.clear();             
        }

          if (maxSubstr == curr[j])
          {
            longest += str1.substr(i - maxSubstr + 1, i + 1);
          }
      }
    }
    swap=curr;
    curr=prev;
    prev=swap;
  }
  delete [] curr;
  delete [] prev;
  return longest.substr(0, maxSubstr);
}