Dada una array de strings arr[] , la tarea es encontrar el par de strings de la array dada cuya longitud del prefijo común más largo entre ellas es máxima. Si existen varias soluciones, imprima cualquiera de ellas.
Ejemplos:
Entrada: arr[] = {“geeksforgeeks”, “geeks”, “geeksforcse”, }
Salida: (geeksforgeeks, geeksforcse)
Explicación:
Todos los pares posibles y su prefijo común más largo son:
(“geeksforgeeks”, “geeks”) tiene el prefijo común más largo = “geeks”
(“geeksforgeeks”, “geeksforcse”) tiene el prefijo común más largo = “geeksfor”
(“geeks”, “geeksforcse”) tiene el prefijo común más largo = “geeks”
Por lo tanto, un par que tiene la longitud máxima del prefijo común más largo es («geeksforgeeks», «geeksforcse»)
Entrada: arr[] = {“abbcbgfh”, “bcdee”, “bcde”, “abbcbde”}
Salida: (abbcbgfh, abbcbde)
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los pares posibles de la array dada y calcular la longitud del prefijo común más largo de cada par . Finalmente, imprima el par que tenga una longitud máxima del prefijo común más largo.
Complejidad de tiempo: O(N 2 * M), donde M denota la longitud de la string más larga
Espacio auxiliar: O(1)
Enfoque eficiente: el problema se puede resolver usando Trie . La idea es recorrer la array dada y, para cada elemento de la array, encontrar la longitud máxima del prefijo más largo presente en Trie e insertar el elemento actual en Trie . Finalmente, imprima el par que tenga una longitud máxima del prefijo común más largo. Siga los pasos a continuación para resolver el problema:
- Cree un Trie que tenga un Node raíz, diga raíz para almacenar cada elemento de la array dada.
- Recorra la array dada y para cada elemento de la array, encuentre la longitud máxima del prefijo más largo presente en Trie e inserte el elemento actual en Trie.
- Finalmente, imprima el par que tenga una longitud máxima del prefijo común más largo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of Trie
struct TrieNode {
// Stores characters of
// each string
TrieNode* child[256];
TrieNode() { child[0] = child[1] = NULL; }
};
// Function to insert a string into Trie
void insertTrie(TrieNode* root, string str)
{
// Stores length of the string
int M = str.length();
// Traverse the string str
for (int i = 0; i < M; i++) {
// If str[i] is not present
// in current path of Trie
if (!root->child[str[i]]) {
// Create a new node
// of Trie
root->child[str[i]] = new TrieNode();
}
// Update root
root = root->child[str[i]];
}
}
// Function to find the maximum length of
// longest common prefix in Trie with str
int findStrLen(TrieNode* root, string str)
{
// Stores length of str
int M = str.length();
// Stores length of longest
// common prefix in Trie with str
int len = 0;
// Traverse the string str
for (int i = 0; i < M; i++) {
// If str[i] is present in
// the current path of Trie
if (root->child[str[i]]) {
// Update len
len++;
// Update root
root = root->child[str[i]];
}
else {
return len;
}
}
return len;
}
// Function to print the pair having maximum
// length of the longest common prefix
void findMaxLenPair(vector<string>& arr, int N)
{
// Stores index of the string having
// maximum length of longest common prefix
int idx = -1;
// Stores maximum length of longest
// common prefix.
int len = 0;
// Create root node of Trie
TrieNode* root = new TrieNode();
// Insert arr[0] into Trie
insertTrie(root, arr[0]);
// Traverse the array.
for (int i = 1; i < N; i++) {
// Stores maximum length of longest
// common prefix in Trie with arr[i]
int temp = findStrLen(root, arr[i]);
// If temp is greater than len
if (temp > len) {
// Update len
len = temp;
// Update idx
idx = i;
}
insertTrie(root, arr[i]);
}
// Traverse array arr[]
for (int i = 0; i < N; i++) {
// Stores length of arr[i]
int M = arr[i].length();
// Check if maximum length of
// longest common prefix > M
if (i != idx && M >= len) {
bool found = true;
// Traverse string arr[i]
// and arr[j]
for (int j = 0; j < len; j++) {
// If current character of both
// string does not match.
if (arr[i][j] != arr[idx][j]) {
found = false;
break;
}
}
// Print pairs having maximum length
// of the longest common prefix
if (found) {
cout << "(" << arr[i] << ", " << arr[idx]
<< ")";
return;
}
}
}
}
// Driver Code
int main()
{
vector<string> arr
= { "geeksforgeeks", "geeks", "geeksforcse" };
int N = arr.size();
findMaxLenPair(arr, N);
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
// class of Trie
class TrieNode {
TrieNode[] child = new TrieNode[256];
TrieNode() {}
}
class GFG {
// Function to insert a string into Trie
private static void insertTrie(TrieNode root,
String str)
{
// Stores length of the string
int M = str.length();
// Traverse the string str
for (int i = 0; i < M; i++) {
// If str[i] is not present
// in current path of Trie
if (root.child[str.charAt(i)] == null) {
// Create a new node
// of Trie
root.child[str.charAt(i)] = new TrieNode();
}
// Update root
root = root.child[str.charAt(i)];
}
}
// Function to find the maximum length of
// longest common prefix in Trie with str
private static int findStrLen(TrieNode root, String str)
{
// Stores length of str
int M = str.length();
// Stores length of longest
// common prefix in Trie with str
int len = 0;
// Traverse the string str
for (int i = 0; i < M; i++) {
// If str[i] is present in
// the current path of Trie
if (root.child[str.charAt(i)] != null) {
// Update len
len++;
// Update root
root = root.child[str.charAt(i)];
}
else {
return len;
}
}
return len;
}
// Function to print the pair having maximum
// length of the longest common prefix
private static void findMaxLenPair(List<String> arr,
int N)
{
// Stores index of the string having
// maximum length of longest common prefix
int idx = -1;
// Stores maximum length of longest
// common prefix.
int len = 0;
// Create root node of Trie
TrieNode root = new TrieNode();
// Insert arr[0] into Trie
insertTrie(root, arr.get(0));
// Traverse the array.
for (int i = 1; i < N; i++) {
// Stores maximum length of longest
// common prefix in Trie with arr[i]
int temp = findStrLen(root, arr.get(i));
// If temp is greater than len
if (temp > len) {
// Update len
len = temp;
// Update idx
idx = i;
}
insertTrie(root, arr.get(i));
}
// Traverse array arr[]
for (int i = 0; i < N; i++) {
// Stores length of arr[i]
int M = arr.get(i).length();
// Check if maximum length of
// longest common prefix > M
if (i != idx && M >= len) {
boolean found = true;
// Traverse string arr[i]
// and arr[j]
for (int j = 0; j < len; j++) {
// If current character of both
// string does not match.
if (arr.get(i).charAt(j)
!= arr.get(idx).charAt(j)) {
found = false;
break;
}
}
// Print pairs having maximum length
// of the longest common prefix
if (found) {
System.out.println("(" + arr.get(i)
+ ", " + arr.get(idx)
+ ")");
return;
}
}
}
}
// Driver Code
public static void main(String[] args)
{
List<String> arr = Arrays.asList(new String[] {
"geeksforgeeks", "geeks", "geeksforcse" });
int N = arr.size();
findMaxLenPair(arr, N);
}
}
Python3
# Python3 program to implement
# the above approach
# class of Trie
class TrieNode:
def __init__(self):
self.child = dict()
# function to insert a string into trie
def insertTrie(root, string):
M = len(string) # stores string length
length = 0
for i in range(M): # traversing string
if string[i] not in root.child:
root.child[string[i]] = TrieNode()
root = root.child[string[i]]
def findStrLen(root, string):
M = len(string)
length = 0
for i in range(M):
if string[i] not in root.child:
length += 1
root = root.child[string[i]]
else:
return length
return length
def findMaxLenPair(arr, N):
idx = -1
length = 0
root = TrieNode()
insertTrie(root, arr[0])
for i in range(1, N):
temp = findStrLen(root, arr[i])
if temp > length:
length = temp
idx = i
insertTrie(root, arr[i])
for i in range(N):
M = len(arr[i])
if (i != idx and M >= length):
found = True
for j in range(length):
if arr[i][j] != arr[idx][j]:
found = False
break
if (found):
print("(" + arr[i] + ", " + arr[idx] + ")")
return
# Driver Code
arr = ["geeksforgeeks", "geeks", "geeksforcse"]
N = len(arr)
findMaxLenPair(arr, N)
# This code is contributed by phasing17
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
// class of Trie
public class GFG
{
public class TrieNode
{
public TrieNode[] child = new TrieNode[256];
public TrieNode() {}
};
// Function to insert a string into Trie
public static void insertTrie(TrieNode root,
String str)
{
// Stores length of the string
int M = str.Length;
// Traverse the string str
for (int i = 0; i < M; i++) {
// If str[i] is not present
// in current path of Trie
if (root.child[str[i]] == null) {
// Create a new node
// of Trie
root.child[str[i]] = new TrieNode();
}
// Update root
root = root.child[str[i]];
}
}
// Function to find the maximum length of
// longest common prefix in Trie with str
public static int findStrLen(TrieNode root, String str)
{
// Stores length of str
int M = str.Length;
// Stores length of longest
// common prefix in Trie with str
int len = 0;
// Traverse the string str
for (int i = 0; i < M; i++) {
// If str[i] is present in
// the current path of Trie
if (root.child[str[i]] != null) {
// Update len
len++;
// Update root
root = root.child[str[i]];
}
else {
return len;
}
}
return len;
}
// Function to print the pair having maximum
// length of the longest common prefix
public static void findMaxLenPair(List<string> arr,
int N)
{
// Stores index of the string having
// maximum length of longest common prefix
int idx = -1;
// Stores maximum length of longest
// common prefix.
int len = 0;
// Create root node of Trie
TrieNode root = new TrieNode();
// Insert arr[0] into Trie
insertTrie(root, arr[0]);
// Traverse the array.
for (int i = 1; i < N; i++) {
// Stores maximum length of longest
// common prefix in Trie with arr[i]
int temp = findStrLen(root, arr[i]);
// If temp is greater than len
if (temp > len) {
// Update len
len = temp;
// Update idx
idx = i;
}
insertTrie(root, arr[i]);
}
// Traverse array arr[]
for (int i = 0; i < N; i++) {
// Stores length of arr[i]
int M = arr[i].Length;
// Check if maximum length of
// longest common prefix > M
if (i != idx && M >= len) {
bool found = true;
// Traverse string arr[i]
// and arr[j]
for (int j = 0; j < len; j++) {
// If current character of both
// string does not match.
if (arr[i][j] != arr[idx][j]) {
found = false;
break;
}
}
// Print pairs having maximum length
// of the longest common prefix
if (found) {
Console.WriteLine("(" + arr[i]+ ", " + arr[idx]+ ")");
return;
}
}
}
}
// Driver Code
public static void Main()
{
List<string> arr = new List<string>() {"geeksforgeeks", "geeks", "geeksforcse" };
int N = arr.Count;
findMaxLenPair(arr, N);
}
}
// THIS CODE IS CONTRIBUTED BY SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program to implement
// the above approach
// Class of Trie
class TrieNode
{
constructor()
{
this.child = Array(256);
}
};
// Function to insert a string into Trie
function insertTrie(root, str)
{
// Stores length of the string
var M = str.length;
// Traverse the string str
for(var i = 0; i < M; i++)
{
// If str[i] is not present
// in current path of Trie
if (root.child[str[i]] == null)
{
// Create a new node
// of Trie
root.child[str[i]] = new TrieNode();
}
// Update root
root = root.child[str[i]];
}
}
// Function to find the maximum length of
// longest common prefix in Trie with str
function findStrLen(root, str)
{
// Stores length of str
var M = str.length;
// Stores length of longest
// common prefix in Trie with str
var len = 0;
// Traverse the string str
for(var i = 0; i < M; i++)
{
// If str[i] is present in
// the current path of Trie
if (root.child[str[i]] != null)
{
// Update len
len++;
// Update root
root = root.child[str[i]];
}
else
{
return len;
}
}
return len;
}
// Function to print the pair having maximum
// length of the longest common prefix
function findMaxLenPair(arr, N)
{
// Stores index of the string having
// maximum length of longest common prefix
var idx = -1;
// Stores maximum length of longest
// common prefix.
var len = 0;
// Create root node of Trie
var root = new TrieNode();
// Insert arr[0] into Trie
insertTrie(root, arr[0]);
// Traverse the array.
for(var i = 1; i < N; i++)
{
// Stores maximum length of longest
// common prefix in Trie with arr[i]
var temp = findStrLen(root, arr[i]);
// If temp is greater than len
if (temp > len)
{
// Update len
len = temp;
// Update idx
idx = i;
}
insertTrie(root, arr[i]);
}
// Traverse array arr[]
for(var i = 0; i < N; i++)
{
// Stores length of arr[i]
var M = arr[i].length;
// Check if maximum length of
// longest common prefix > M
if (i != idx && M >= len)
{
var found = true;
// Traverse string arr[i]
// and arr[j]
for(var j = 0; j < len; j++)
{
// If current character of both
// string does not match.
if (arr[i][j] != arr[idx][j])
{
found = false;
break;
}
}
// Print pairs having maximum length
// of the longest common prefix
if (found)
{
document.write("(" + arr[i] +
", " + arr[idx] + ")");
return;
}
}
}
}
// Driver Code
var arr = [ "geeksforgeeks", "geeks",
"geeksforcse" ];
var N = arr.length;
findMaxLenPair(arr, N);
// This code is contributed by rrrtnx
</script>
Producción:
(geeksforgeeks, geeksforcse)
Complejidad de tiempo: O (N * M), donde M denota la longitud de la string más larga
Espacio auxiliar: 0 (N * 256)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA