How To Find largest common substring from an array of strings in C++

In this tutorial we will learn how to  find largest common substring from an array of strings with some cool examples.

SO first the question arises what is an array and a string

An Array is a data structure that is used to store a collection of elements that are of same data type .

It helps us to store various values of same type under same name

A String is a sequence of characters which is used to represent text or data in programming

Find largest common substring from an array of strings

Let’s learn how we perform this for this we use dynamic programming techniques( dynamic programming is used by breaking a problem into smaller chunks ) .

The  basic idea is to take a word from a list as reference and form all its substrings .Then we will iterate over the entire list and check if generated substring occurs in all of them.

now lets see how dynamic programming is used here or the steps used to solve our problem

• We initialize a result string to store the largest common substring found so far.
• Then we initialize a 2D dynamic programming table to store the lengths of common substrings.
• We will then have to Iterate over each pair of strings in the array.
• Then For each pair of strings, update the dynamic programming table with the lengths of common substrings
• Finally we Update the result string if a longer common substring is found.
• Thus after we have iterated over all the pairs of strings we return the result string as largest common substring

• #include <bits/stdc++.h>
  using namespace std;
  
  
  string findstem(vector<string> arr)
  {
      
      int n = arr.size();
  
  
      string s = arr[0];
      int len = s.length();
  
      string res = "";
  
      for (int i = 0; i < len; i++) {
          for (int j = i + 1; j <= len; j++) {
          
              string stem = s.substr(i, j);
              int k = 1;
              for (k = 1; k < n; k++) {
              
                  if (arr[k].find(stem) == std::string::npos)
                      break;
              }
  
          
              if (k == n && res.length() < stem.length())
                  res = stem;
          }
      }
  
      return res;
  }
  
  
  int main()
  {
      vector<string> arr{ "grace", "graceful", "disgraceful",
                          "gracefully" };
  
  
      string stems = findstem(arr);
      cout << stems << endl;
  }
  
  

  the above code will give the output as

grace