Substring común más larga en una array de strings

Se nos da una lista de palabras que comparten una raíz común, es decir, las palabras se originan de la misma palabra, por ejemplo: las palabras tristeza, tristemente y triste se originan todas de la raíz ‘triste’ . 
Nuestra tarea es encontrar y devolver la substring común más larga, también conocida como raíz de esas palabras. En caso de empate, elegimos el más pequeño en orden alfabético. 

Ejemplos: 

Input : grace graceful disgraceful gracefully
Output : grace

Input : sadness sad sadly
Output : sad

La idea es tomar cualquier palabra de la lista como referencia y formar todas sus substrings e iterar sobre toda la lista comprobando si la substring generada aparece en todas ellas.

A continuación se muestra la implementación de la idea anterior:

// C++ program to find the stem of given list of
// words
#include <bits/stdc++.h>
using namespace std;
 
// function to find the stem (longest common
// substring) from the string array
string findstem(vector<string> arr)
{
    // Determine size of the array
    int n = arr.size();
 
    // Take first word from array as reference
    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++) {
            // generating all possible substrings
            // of our reference string arr[0] i.e s
            string stem = s.substr(i, j);
            int k = 1;
            for (k = 1; k < n; k++) {
                // Check if the generated stem is
                // common to all words
                if (arr[k].find(stem) == std::string::npos)
                    break;
            }
 
            // If current substring is present in
            // all strings and its length is greater
            // than current result
            if (k == n && res.length() < stem.length())
                res = stem;
        }
    }
 
    return res;
}
 
// Driver code
int main()
{
    vector<string> arr{ "grace", "graceful", "disgraceful",
                        "gracefully" };
 
    // Function call
    string stems = findstem(arr);
    cout << stems << endl;
}
 
// This code is contributed by
// sanjeev2552

// Java program to find the stem of given list of
// words
import java.io.*;
import java.util.*;
 
class stem {
 
    // function to find the stem (longest common
    // substring) from the string  array
    public static String findstem(String arr[])
    {
        // Determine size of the array
        int n = arr.length;
 
        // Take first word from array as reference
        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++) {
 
                // generating all possible substrings
                // of our reference string arr[0] i.e s
                String stem = s.substring(i, j);
                int k = 1;
                for (k = 1; k < n; k++)
 
                    // Check if the generated stem is
                    // common to all words
                    if (!arr[k].contains(stem))
                        break;
 
                // If current substring is present in
                // all strings and its length is greater
                // than current result
                if (k == n && res.length() < stem.length())
                    res = stem;
            }
        }
 
        return res;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        String arr[] = { "grace", "graceful",
                        "disgraceful","gracefully" };
       
        // Function call
        String stems = findstem(arr);
        System.out.println(stems);
    }
}

# Python 3 program to find the stem
# of given list of words
 
# function to find the stem (longest
# common substring) from the string array
 
 
def findstem(arr):
 
    # Determine size of the array
    n = len(arr)
 
    # Take first word from array
    # as reference
    s = arr[0]
    l = len(s)
 
    res = ""
 
    for i in range(l):
        for j in range(i + 1, l + 1):
 
            # generating all possible substrings
            # of our reference string arr[0] i.e s
            stem = s[i:j]
            k = 1
            for k in range(1, n):
 
                # Check if the generated stem is
                # common to all words
                if stem not in arr[k]:
                    break
 
            # If current substring is present in
            # all strings and its length is greater
            # than current result
            if (k + 1 == n and len(res) < len(stem)):
                res = stem
 
    return res
 
 
# Driver Code
if __name__ == "__main__":
 
    arr = ["grace", "graceful",
           "disgraceful", "gracefully"]
     
    # Function call
    stems = findstem(arr)
    print(stems)
 
# This code is contributed by ita_c

// C# program to find the stem of given list of
// words
using System;
using System.Collections.Generic;
 
class stem
{
    // function to find the stem (longest common
    // substring) from the string array
    public static String findstem(String []arr)
    {
        // Determine size of the array
        int n = arr.Length;
 
        // Take first word from array as reference
        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++)
            {
 
                // generating all possible substrings
                // of our reference string arr[0] i.e s
                String stem = s.Substring(i, j-i);
                int k = 1;
                for (k = 1; k < n; k++)
 
                    // Check if the generated stem is
                    // common to all words
                    if (!arr[k].Contains(stem))
                        break;
                 
                // If current substring is present in
                // all strings and its length is greater
                // than current result
                if (k == n && res.Length < stem.Length)
                    res = stem;
            }
        }
 
        return res;
    }
 
    // Driver Code
    public static void Main(String []args)
    {
        String []arr = { "grace", "graceful", "disgraceful",
                                            "gracefully" };
        // Function call
        String stems = findstem(arr);
        Console.WriteLine(stems);
    }
}
 
// This code contributed by Rajput-Ji

<?php
// PHP program to find the stem of given list of
// words
 
    // function to find the stem (longest common
    // substring) from the string array
    function findstem($arr)
    {
        // Determine size of the array
        $n = count($arr);
 
        // Take first word from array as reference
        $s = $arr[0];
        $len = strlen($s);
         
        $res = "";
 
        for ($i = 0; $i < $len; $i++)
        {
            for ($j = $i+1; $j <=$len; $j++)
            {
 
                // generating all possible substrings
                // of our reference string arr[0] i.e s
                $stem = substr($s,$i, $j-$i);
                 
                $k = 1;
                for ($k = 1; $k < $n; $k++)
 
                    // Check if the generated stem is
                    // common to all words
                    if (!strpos($arr[$k],$stem))
                        break;
                 
                // If current substring is present in
                // all strings and its length is greater
                // than current result
                if ($k <= $n && strlen($res) < strlen($stem))
                    $res = $stem;
                 
            }
        }
 
        return $res;
    }
 
    // Driver Code
    $arr = array( "grace", "graceful",
                 "disgraceful", "gracefully" );
 
    // Function call
    $stems = findstem($arr);
    print($stems);
     
// This code is contributed by mits
?>

grace

Este artículo es una contribución de DANISH KALEEM . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.