Longest Common Substring in an Array of Strings | C ++ program to find the stem of given list of words ; function to find the stem ( longest commonsubstring ) from the string array ; Determine size of the array ; Take first word from array as reference ; generating all possible substrings of our reference string arr [ 0 ] i . e s ; Check if the generated stem is common to all words ; If current substring is present in all strings and its length is greater than current result ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE 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 ; }