Dado un conjunto de strings, encuentre el prefijo común más largo.
Ejemplos:
Input : {“geeksforgeeks”, “geeks”, “geek”, “geezer”}
Output : "gee"
Input : {"apple", "ape", "april"}
Output : "ap"
Empezamos con un ejemplo. Supongamos que hay dos strings: «geeksforgeeks» y «geeks». ¿Cuál es el prefijo común más largo en ambos? Es «frikis».
Ahora introduzcamos otra palabra «geek». Entonces, ¿cuál es el prefijo común más largo en estas tres palabras? Es «geek»
. Podemos ver que el prefijo común más largo tiene la propiedad asociativa, es decir,
LCP(string1, string2, string3)
= LCP (LCP (string1, string2), string3)
Like here
LCP (“geeksforgeeks”, “geeks”, “geek”)
= LCP (LCP (“geeksforgeeks”, “geeks”), “geek”)
= LCP (“geeks”, “geek”) = “geek”
Entonces podemos hacer uso de la propiedad asociativa anterior para encontrar el LCP de las strings dadas. Calculamos uno por uno el LCP de cada una de las strings dadas con el LCP hasta ahora. El resultado final será nuestro prefijo común más largo de todas las strings.
Tenga en cuenta que es posible que las strings dadas no tengan un prefijo común. Esto sucede cuando el primer carácter de todas las strings no es el mismo.
Mostramos el algoritmo con las strings de entrada: «geeksforgeeks», «geeks», «geek», «geezer» en la siguiente figura.
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 Utility Function to find the common prefix between
// strings- str1 and str2
string commonPrefixUtil(string& str1, string& str2)
{
string result = "";
int len = min(str1.length(), str2.length());
// Compare str1 and str2
for (int i = 0; i < len; i++)
{
if (str1[i] != str2[i])
break;
result += str1[i];
}
return (result);
}
// A Function that returns the longest common prefix
// from the array of strings
string commonPrefix (string arr[], int n)
{
string prefix = arr[0];
for (int i=1; i < n; i++)
prefix = commonPrefixUtil(prefix, arr[i]);
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())
printf ("The longest common prefix is - %s",
ans.c_str());
else
printf("There is no common prefix");
return (0);
}
Java
// Java Program to find the longest common prefix
class GFG {
// A Utility Function to find the common prefix between
// strings- str1 and str2
static String commonPrefixUtil(String str1, String str2) {
String result = "";
int n1 = str1.length(), n2 = str2.length();
// Compare str1 and str2
for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) {
if (str1.charAt(i) != str2.charAt(j)) {
break;
}
result += str1.charAt(i);
}
return (result);
}
// A Function that returns the longest common prefix
// from the array of strings
static String commonPrefix(String arr[], int n) {
String prefix = arr[0];
for (int i = 1; i <= n - 1; i++) {
prefix = commonPrefixUtil(prefix, arr[i]);
}
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.printf("The longest common prefix is - %s",
ans);
} else {
System.out.printf("There is no common prefix");
}
}
}
// This code is contributed by 29AjayKumar
Python3
# A python3 Program to find the longest
# common prefix
# A Utility Function to find the common
# prefix between strings- str1 and str2
def commonPrefixUtil(str1, str2):
result = "";
n1 = len(str1)
n2 = len(str2)
# Compare str1 and str2
i = 0
j = 0
while i <= n1 - 1 and j <= n2 - 1:
if (str1[i] != str2[j]):
break
result += str1[i]
i += 1
j += 1
return (result)
# A Function that returns the longest
# common prefix from the array of strings
def commonPrefix (arr, n):
prefix = arr[0]
for i in range (1, n):
prefix = commonPrefixUtil(prefix, arr[i])
return (prefix)
# Driver Code
if __name__ =="__main__":
arr = ["geeksforgeeks", "geeks",
"geek", "geezer"]
n = len(arr)
ans = commonPrefix(arr, n)
if (len(ans)):
print ("The longest common prefix is -",
ans);
else:
print("There is no common prefix")
# This code is contributed by ita_c
C#
// C# Program to find the longest
// common prefix
using System;
class GFG
{
// A Utility Function to find
// the common prefix between
// strings- str1 and str2
static String commonPrefixUtil(String str1,
String str2)
{
String result = "";
int n1 = str1.Length,
n2 = str2.Length;
// Compare str1 and str2
for (int i = 0, j = 0;
i <= n1 - 1 && j <= n2 - 1;
i++, j++)
{
if (str1[i] != str2[j])
{
break;
}
result += str1[i];
}
return (result);
}
// A Function that returns the longest
// common prefix from the array of strings
static String commonPrefix(String []arr, int n)
{
String prefix = arr[0];
for (int i = 1; i <= n - 1; i++)
{
prefix = commonPrefixUtil(prefix,
arr.GetValue(i).ToString());
}
return (prefix);
}
// Driver Code
public static void Main()
{
String []arr = {"geeksforgeeks", "geeks",
"geek", "geezer"};
int n = arr.Length;
String ans = commonPrefix(arr, n);
if (ans.Length > 0)
{
Console.Write("The longest common " +
"prefix is - " + ans);
}
else
{
Console.Write("There is no common prefix");
}
}
}
// This code is contributed
// by 29AjayKumar
Javascript
<script>
// Javascript Program to find the longest common prefix
// A Utility Function to find the common prefix between
// strings- str1 and str2
function commonPrefixUtil(str1,str2)
{
let result = "";
let n1 = str1.length, n2 = str2.length;
// Compare str1 and str2
for (let i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) {
if (str1[i] != str2[j]) {
break;
}
result += str1[i];
}
return (result);
}
// A Function that returns the longest common prefix
// from the array of strings
function commonPrefix(arr,n)
{
let prefix = arr[0];
for (let i = 1; i <= n - 1; i++) {
prefix = commonPrefixUtil(prefix, arr[i]);
}
return (prefix);
}
// Driver program to test above function
let arr=["geeksforgeeks", "geeks",
"geek", "geezer"];
let n = arr.length;
let ans = commonPrefix(arr, n);
if (ans.length > 0) {
document.write("The longest common prefix is - ",
ans);
} else {
document.write("There is no common prefix ");
}
// This code is contributed by rag2127
</script>
The longest common prefix is - gee
Complejidad de tiempo: dado que estamos iterando a través de todas las strings y para cada string estamos iterando a través de cada carácter, podemos decir que la complejidad de tiempo es O (NM) donde,
N = Number of strings M = Length of the largest string
Espacio auxiliar: para almacenar la string de prefijos más larga, estamos asignando un espacio que es O (M).
¿Cómo mejorar esto?
Consulte Prefijo común más largo | Conjunto 2 (Coincidencia de personaje por personaje)
Este artículo es una contribución de Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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.
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