La substring más grande de str2 que es un prefijo de str1

Dadas dos strings str1 y str2 , la tarea es encontrar el prefijo más largo de str1 que está presente como una substring de la string str2 . Imprima el prefijo si es posible, de lo contrario imprima -1.
Ejemplos: 
 

Entrada: str1 = “geeksfor”, str2 = “forgeeks” 
Salida: geeks 
Todos los prefijos de str1 que están presentes en str2 
son “g”, “ge”, “gee”, “geek” y “geeks”.
Entrada: str1 = «abc», str2 = «def» 
Salida: -1 
 

Enfoque: verifique si str1 está presente como una substring en str2 . En caso afirmativo, str1 es la string requerida; de lo contrario, elimine el último carácter de str1 y repita estos pasos hasta que la string str1 quede vacía o se encuentre la string requerida.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <iostream>
using namespace std;
 
// Function to return the largest substring
// in str2 which is a prefix of str1
string findPrefix(string str1, string str2)
{
 
    // To store the index in str2 which
    // matches the prefix in str1
    int pos = -1;
 
    // While there are characters left in str1
    while (!str1.empty()) {
 
        // If the prefix is not found in str2
        if (str2.find(str1) == string::npos)
 
            // Remove the last character
            str1.pop_back();
        else {
 
            // Prefix found
            pos = str2.find(str1);
            break;
        }
    }
 
    // No substring found in str2 that
    // matches the prefix of str1
    if (pos == -1)
        return "-1";
 
    return str1;
}
 
// Driver code
int main()
{
    string str1 = "geeksfor";
    string str2 = "forgeeks";
 
    cout << findPrefix(str1, str2);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the largest substring
// in str2 which is a prefix of str1
static String findPrefix(String str1,
                         String str2)
{
 
    // To store the index in str2 which
    // matches the prefix in str1
    boolean pos = false;
 
    // While there are characters left in str1
    while (str1.length() > 0)
    {
 
        // If the prefix is not found in str2
        if (!str2.contains(str1))
 
            // Remove the last character
            str1 = str1.substring(0, str1.length() - 1);
        else
        {
 
            // Prefix found
            pos = str2.contains(str1);
            break;
        }
    }
 
    // No substring found in str2 that
    // matches the prefix of str1
    if (pos == false)
        return "-1";
 
    return str1;
}
 
// Driver code
public static void main(String[] args)
{
    String str1 = "geeksfor";
    String str2 = "forgeeks";
 
    System.out.println(findPrefix(str1, str2));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
import operator
 
# Function to return the largest substring
# in str2 which is a prefix of str1
def findPrefix(str1, str2):
     
    # To store the index in str2 which
    # matches the prefix in str1
    pos = False;
 
    # While there are characters left in str1
    while (len(str1) != 0):
 
        # If the prefix is not found in str2
        if operator.contains(str2, str1) != True:
 
            # Remove the last character
            str1 = str1[0: len(str1) - 1];
        else:
 
            # Prefix found
            pos = operator.contains(str2, str1);
            break;
 
    # No substring found in str2 that
    # matches the prefix of str1
    if (pos == False):
        return "-1";
 
    return str1;
 
# Driver code
if __name__ == '__main__':
    str1 = "geeksfor";
    str2 = "forgeeks";
 
    print(findPrefix(str1, str2));
 
# This code is contributed by 29AjayKumar

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the largest substring
// in str2 which is a prefix of str1
static String findPrefix(String str1,
                         String str2)
{
 
    // To store the index in str2 which
    // matches the prefix in str1
    bool pos = false;
 
    // While there are characters left in str1
    while (str1.Length > 0)
    {
 
        // If the prefix is not found in str2
        if (!str2.Contains(str1))
 
            // Remove the last character
            str1 = str1.Substring(0, str1.Length - 1);
        else
        {
 
            // Prefix found
            pos = str2.Contains(str1);
            break;
        }
    }
 
    // No substring found in str2 that
    // matches the prefix of str1
    if (pos == false)
        return "-1";
 
    return str1;
}
 
// Driver code
public static void Main(String[] args)
{
    String str1 = "geeksfor";
    String str2 = "forgeeks";
 
    Console.WriteLine(findPrefix(str1, str2));
}
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript implementation of the approach
 
// Function to return the largest substring
// in str2 which is a prefix of str1
function findPrefix(str1, str2)
{
 
    // To store the index in str2 which
    // matches the prefix in str1
    var pos = -1;
 
    // While there are characters left in str1
    while (str1.length!=0) {
 
        // If the prefix is not found in str2
        if (!str2.includes(str1))
 
            // Remove the last character
            str1 = str1.substring(0,str1.length-1)
        else {
 
            // Prefix found
            pos = str2.includes(str1);
            break;
        }
    }
 
    // No substring found in str2 that
    // matches the prefix of str1
    if (pos == -1)
        return "-1";
 
    return str1;
}
 
// Driver code
var str1 = "geeksfor";
var str2 = "forgeeks";
document.write( findPrefix(str1, str2));
 
// This code is contributed by rutvik_56.
</script>

geeks

Complejidad de tiempo: O(N * M) donde N, M son las longitudes de strings dadas.