Prefijo común más largo usando búsqueda binaria – Part 1

Dado un conjunto de strings, encuentre el prefijo común más largo. 
 

Input  : {“geeksforgeeks”, “geeks”, “geek”, “geezer”}
Output : "gee"

Input  : {"apple", "ape", "april"}
Output : "ap"


Input  : {"abcd"}
Output : "abcd"

Enfoques anteriores: coincidencia palabra por palabra, coincidencia de carácter por carácter , divide y vencerás  En este artículo, se analiza 
un enfoque que utiliza la búsqueda binaria .
Pasos: 
 

  1. Encuentre la cuerda que tiene la longitud mínima. Sea esta longitud L .
  2. Realice una búsqueda binaria en cualquier string (desde la array de strings de entrada). Tomemos la primera string y hagamos una búsqueda binaria en los caracteres del índice – 0 a L-1 .
  3. Inicialmente, tome bajo = 0 y alto = L-1 y divida la string en dos mitades: izquierda (bajo a medio) y derecha (medio + 1 a alto) .
  4. Compruebe si todos los caracteres de la mitad izquierda están presentes en los índices correspondientes (bajo a medio) de todas las strings o no. Si está presente, agregamos esta mitad a nuestra string de prefijo y buscamos en la mitad derecha con la esperanza de encontrar un prefijo más largo (se garantiza que hay una string de prefijo común).
  5. De lo contrario, si todos los caracteres en la mitad izquierda no están presentes en los índices correspondientes (bajo a medio) en todas las strings, entonces no necesitamos mirar la mitad derecha ya que hay algunos caracteres en la mitad izquierda que no es parte de la string de prefijos más larga. Entonces, de hecho, miramos la mitad izquierda con la esperanza de encontrar una string de prefijo común. (Es posible que no encontremos ninguna string de prefijo común)

Ilustración de algoritmo considerando strings como – “geeksforgeeks”, “geeks”, “geek”, “geezer”
 

Longest Common Prefix using Binary Search

Longest Common Prefix using Binary Search

A continuación se muestra la implementación del enfoque anterior. 
 

C++

//  A C++ Program to find the longest common prefix
#include<bits/stdc++.h>
using namespace std;
 
// A Function to find the string having the minimum
// length and returns that length
int findMinLength(string arr[], int n)
{
    int min = INT_MAX;
 
    for (int i=0; i<=n-1; i++)
        if (arr[i].length() < min)
            min = arr[i].length();
    return(min);
}
 
bool allContainsPrefix(string arr[], int n, string str,
                       int start, int end)
{
    for (int i=0; i<=n-1; i++)
        for (int j=start; j<=end; j++)
            if (arr[i][j] != str[j])
                return (false);
    return (true);
}
 
// A Function that returns the longest common prefix
// from the array of strings
string commonPrefix(string arr[], int n)
{
    int index = findMinLength(arr, n);
    string prefix; // Our resultant string
 
    // We will do an in-place binary search on the
    // first string of the array in the range 0 to
    // index
    int low = 0, high = index;
 
    while (low <= high)
    {
        // Same as (low + high)/2, but avoids overflow
        // for large low and high
        int mid = low + (high - low) / 2;
 
        if (allContainsPrefix (arr, n, arr[0], low, mid))
        {
            // If all the strings in the input array contains
            // this prefix then append this substring to
            // our answer
            prefix = prefix + arr[0].substr(low, mid-low+1);
 
            // And then go for the right part
            low = mid + 1;
        }
 
        else // Go for the left part
            high = mid - 1;
    }
 
    return (prefix);
}
 
// Driver program to test above function
int main()
{
    string arr[] = {"geeksforgeeks", "geeks",
                    "geek", "geezer"};
    int n = sizeof (arr) / sizeof (arr[0]);
 
    string ans = commonPrefix(arr, n);
 
    if (ans.length())
        cout << "The longest common prefix is "
             << ans;
    else
        cout << "There is no common prefix";
    return (0);
}

Java

// A Java Program to find the longest common prefix
 
class GFG {
 
    // A Function to find the string having the
    // minimum length and returns that length
    static int findMinLength(String arr[], int n)
    {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i <= (n - 1); i++)
        {
            if (arr[i].length() < min) {
                min = arr[i].length();
            }
        }
        return min;
    }
 
    static boolean allContainsPrefix(String arr[], int n,
                         String str, int start, int end)
    {
        for (int i = 0; i <= (n - 1); i++)
        {
            String arr_i = arr[i];
             
            for (int j = start; j <= end; j++)
                if (arr_i.charAt(j) != str.charAt(j))
                    return false;
        }
        return true;
    }
 
    // A Function that returns the longest common prefix
    // from the array of strings
    static String commonPrefix(String arr[], int n)
    {
        int index = findMinLength(arr, n);
        String prefix = ""; // Our resultant string
 
        // We will do an in-place binary search on the
        // first string of the array in the range 0 to
        // index
        int low = 0, high = index-1;
        while (low <= high) {
             
            // Same as (low + high)/2, but avoids
            // overflow for large low and high
            int mid = low + (high - low) / 2;
 
            if (allContainsPrefix(arr, n, arr[0], low,
                                                  mid))
            {
                // If all the strings in the input array
                // contains this prefix then append this
                // substring to our answer
                prefix = prefix + arr[0].substring(low,
                                          mid + 1);
 
                // And then go for the right part
                low = mid + 1;
            }
            else // Go for the left part
            {
                high = mid - 1;
            }
        }
 
        return prefix;
    }
 
    // Driver program to test above function
    public static void main(String args[])
    {
        String arr[] = {"geeksforgeeks", "geeks",
                               "geek", "geezer"};
        int n = arr.length;
 
        String ans = commonPrefix(arr, n);
         
        if (ans.length() > 0)
            System.out.println("The longest common"
                            + " prefix is " + ans);
        else
            System.out.println("There is no common"
                                      + " prefix");
    }
}
 
// This code is contributed by Indrajit Sinha.

Python3

# A Python3 Program to find
# the longest common prefix
 
# A Function to find the string having the
# minimum length and returns that length
def findMinLength(strList):
    return len(min(arr, key = len))
 
def allContainsPrefix(strList, str,
                      start, end):
    for i in range(0, len(strList)):
        word = strList[i]
        for j in range(start, end + 1):
            if word[j] != str[j]:
                return False
    return True
 
# A Function that returns the longest
# common prefix from the array of strings
def CommonPrefix(strList):
    index = findMinLength(strList)
    prefix = ""     # Our resultant string
 
    # We will do an in-place binary search
    # on the first string of the array
    # in the range 0 to index
    low, high = 0, index - 1
    while low <= high:
 
        # Same as (low + high)/2, but avoids
        # overflow for large low and high
        mid = int(low + (high - low) / 2)
        if allContainsPrefix(strList,  
                             strList[0], low, mid):
             
            # If all the strings in the input array
            # contains this prefix then append this
            # substring to our answer
            prefix = prefix + strList[0][low:mid + 1]
 
            # And then go for the right part
            low = mid + 1
        else:
             
            # Go for the left part
            high = mid - 1
 
    return prefix
 
# Driver Code
arr = ["geeksforgeeks", "geeks",
       "geek", "geezer"]
lcp = CommonPrefix(arr)
 
if len(lcp) > 0:
    print ("The longest common prefix is " +
                                 str(lcp))
else:
    print ("There is no common prefix")
 
# This code is contributed by garychan8523

C#

// C# Program to find the longest common prefix using System;
using System;               
public class GFG {
  
    // A Function to find the string having the
    // minimum length and returns that length
    static int findMinLength(string []arr, int n)
    {
        int min = int.MaxValue;
        for (int i = 0; i <= (n - 1); i++)
        {
            if (arr[i].Length < min) {
                min = arr[i].Length;
            }
        }
        return min;
    }
  
    static bool allContainsPrefix(string []arr, int n,
                         string str, int start, int end)
    {
        for (int i = 0; i <= (n - 1); i++)
        {
            string arr_i = arr[i];
              
            for (int j = start; j <= end; j++)
                if (arr_i[j] != str[j])
                    return false;
        }
        return true;
    }
  
    // A Function that returns the longest common prefix
    // from the array of strings
    static string commonPrefix(string []arr, int n)
    {
        int index = findMinLength(arr, n);
        string prefix = ""; // Our resultant string
  
        // We will do an in-place binary search on the
        // first string of the array in the range 0 to
        // index
        int low = 0, high = index;
        while (low <= high) {
              
            // Same as (low + high)/2, but avoids
            // overflow for large low and high
            int mid = low + (high - low) / 2;
  
            if (allContainsPrefix(arr, n, arr[0], low,
                                                  mid))
            {
                // If all the strings in the input array
                // contains this prefix then append this
                // substring to our answer
                prefix = prefix + arr[0].Substring(low,
                                          mid + 1);
  
                // And then go for the right part
                low = mid + 1;
            }
            else // Go for the left part
            {
                high = mid - 1;
            }
        }
  
        return prefix;
    }
  
    // Driver program to test above function
    public static void Main()
    {
        string []arr = {"geeksforgeeks", "geeks",
                               "geek", "geezer"};
        int n = arr.Length;
 
        string ans = commonPrefix(arr, n);
          
        if (ans.Length > 0)
            Console.WriteLine("The longest common"
                            + " prefix is - " + ans);
        else
            Console.WriteLine("There is no common"
                                      + " prefix");
    }
}
  
// This code is contributed by PrinciRaj1992

Javascript

<script>
//  A JavaScript Program to find the longest common prefix
 
// A Function to find the string having the minimum
// length and returns that length
function findMinLength( arr , n)
{
    var min = Number.POSITIVE_INFINITY;
    for (let i=0; i<=n-1; i++)
        if (arr[i].length< min)
            min = arr[i].length;
           
    return(min);
}
 
function allContainsPrefix( arr, n,  str,
                       start,  end)
{
    for (let i=0; i<=n-1; i++)
        for (let j=start; j<=end; j++)
            if (arr[i][j] != str[j])
                return (false);
    return (true);
}
 
// A Function that returns the longest common prefix
// from the array of strings
function commonPrefix( arr , n)
{
    var index = findMinLength(arr, n);
    var prefix = ""; // Our resultant string
 
    // We will do an in-place binary search on the
    // first string of the array in the range 0 to
    // index
    var  low = 0, high = index;
 
    while (low <= high)
    {
        // Same as (low + high)/2, but avoids overflow
        // for large low and high
        var mid = low + (high - low) / 2;
 
        if (allContainsPrefix (arr, n, arr[0], low, mid))
        {
            // If all the strings in the input array contains
            // this prefix then append this substring to
            // our answer
            prefix = prefix + arr[0].substr(low, mid-low+1);
 
            // And then go for the right part
            low = mid + 1;
        }
 
        else // Go for the left part
            high = mid - 1;
    }
 
    return (prefix);
     
}
 
// Driver program to test above function
 
    var arr= new Array("geeksforgeeks", "geeks",
              "geek", "geezer");
    var n = arr.length;
    var ans = commonPrefix(arr, n);
 
    if (ans.length)
       document.write("The longest common prefix is "
             + ans);
    else
        document.write("There is no common prefix");
     
// This code is contributed by ukasp.
</script>

Producción : 
 

The longest common prefix is - gee

Complejidad temporal: 
la relación de recurrencia es 
 

T(M) = T(M/2) + O(MN) 

dónde 
 

N = Number of strings
M = Length of the largest string

Entonces podemos decir que la complejidad del tiempo es O(NM log M)
Espacio auxiliar: para almacenar la string de prefijo más larga estamos asignando espacio que es O(N) donde, N = longitud de la string más grande entre todas las strings 
Este artículo es aportado por Rachit Belwariar . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *