Dada una lista de strings, la tarea es encontrar la suma de todos los LCP (prefijo común más largo) de longitud máxima seleccionando dos strings a la vez.
Ejemplos:
Entrada: str[] = {babab, ababb, abbab, aaaaa, babaa, babbb}
Salida: 6
Explicación:
Elija la 1.ª y 5.ª string => longitud de LCP = 4,
elija la 2.ª y 3.ª string => longitud de LCP = 2
Suma de LCP = 4 + 2 = 6
Entrada: str = [“aa”, “aaaa”, “aaaaaaaa”, “aaaabaaaa”, “aaaabaaa”]
Salida: 7
Explicación:
Elija la 3.ª (aaaaaaaa) y la 4.ª string (aaaabaaaa) => longitud de LCP (aaaa) = 4,
elija la segunda (aaaa) y la quinta (aaabaaa) string => longitud de LCP (aaa) = 3
Suma de LCP = 4 + 3 = 7
Enfoque ingenuo:
- Ordenar la lista de strings en orden decreciente de su longitud
- Luego tome la primera string de la lista y busque el prefijo común más largo con todas las demás strings restantes en la lista y guárdela en la array
- Elija el valor máximo de la array y agréguelo a la respuesta variable y elimine el par de strings de la lista correspondiente a esa suma
- Repita los procedimientos anteriores para todas las strings siguientes hasta que la lista esté vacía o llegue a la última string.
- La respuesta variable tiene la suma requerida de todos los LCP de longitud máxima
Complejidad de tiempo: O(M*N 2 ), donde M = longitud máxima de string y N = número de strings.
Enfoque eficiente:
se puede obtener una solución eficiente utilizando una estructura de datos Trie . Para encontrar el número de caracteres comunes entre las strings, usaremos la variable ‘visitado’ para realizar un seguimiento de cuántas veces se visita un carácter.
Los siguientes son los pasos:
- Inserte una lista de strings en trie de modo que cada string en la lista se inserte como un Node trie individual.
- Para todos los prefijos de longitud máxima, cuente los pares desde el Node más profundo del trie.
- Utilice el recorrido de búsqueda primero en profundidad (DFS) en el intento para contar los pares desde el Node más profundo.
- Si el valor del Node visitado es más de uno, significa que hay dos o más strings que tienen un prefijo común hasta ese Node.
- Agregue el valor de ese Node visitado a un recuento variable.
- Disminuya el valor de ese Node visitado de los Nodes actuales y anteriores de modo que el par de palabras elegido para el cálculo deba eliminarse.
- Repita los pasos anteriores para todos los Nodes y devuelva el valor de recuento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find Sum of all LCP
// of maximum length by selecting
// any two Strings at a time
#include <bits/stdc++.h>
using namespace std;
class TrieNode {
public:
char val;
// Using map to store the pointers
// of children nodes for dynamic
// implementation, for making the
// program space efficient
map<char, TrieNode*> children;
// Counts the number of times the node
// is visited while making the trie
int visited;
// Initially visited value for all
// nodes is zero
TrieNode(char x)
{
val = x;
visited = 0;
}
};
class Trie {
public:
TrieNode* head;
// Head node of the trie is initialize
// as '\0', after this all strings add
Trie()
{
head = new TrieNode('\0');
}
// Function to insert the strings in
// the trie
void addWord(string s)
{
TrieNode* temp = head;
const unsigned int n = s.size();
for (int i = 0; i < n; i++) {
// Inserting character-by-character
char ch = s[i];
// If the node of ch is not present in
// map make a new node and add in map
if (!temp->children[ch]) {
temp->children[ch] = new TrieNode(ch);
}
temp = temp->children[ch];
temp->visited++;
}
}
// Recursive function to calculate the
// answer argument is passed by reference
int dfs(TrieNode* node, int& ans, int depth)
{
// To store changed visited values from
// children of this node i.e. number of
// nodes visited by its children
int vis = 0;
for (auto child : node->children) {
vis += dfs(child.second, ans, depth + 1);
}
// Updating the visited variable, telling
// number of nodes that have
// already been visited by its children
node->visited -= vis;
int string_pair = 0;
// If node->visited > 1, means more than
// one string has prefix up till this node
// common in them
if (node->visited > 1) {
// Number of string pair with current
// node common in them
string_pair = (node->visited / 2);
ans += (depth * string_pair);
// Updating visited variable of current node
node->visited -= (2 * string_pair);
}
// Returning the total number of nodes
// already visited that needs to be
// updated to previous node
return (2 * string_pair + vis);
}
// Function to run the dfs function for the
// first time and give the answer variable
int dfshelper()
{
// Stores the final answer
// as sum of all depths
int ans = 0;
dfs(head, ans, 0);
return ans;
}
};
// Driver Function
int main()
{
Trie T;
string str[]
= { "babab", "ababb", "abbab",
"aaaaa", "babaa", "babbb" };
int n = 6;
for (int i = 0; i < n; i++) {
T.addWord(str[i]);
}
int ans = T.dfshelper();
cout << ans << endl;
return 0;
}
Java
// Java program to find Sum of all LCP
// of maximum length by selecting
// any two Strings at a time
import java.util.*;
class GFG
{
static class TrieNode
{
char val;
// Using map to store the pointers
// of children nodes for dynamic
// implementation, for making the
// program space efficient
HashMap<Character, TrieNode> children;
// Counts the number of times the node
// is visited while making the trie
int visited;
// Initially visited value for all
// nodes is zero
TrieNode(char x)
{
val = x;
visited = 0;
children = new HashMap<>();
}
}
static class Trie
{
TrieNode head;
int ans;
// Head node of the trie is initialize
// as '\0', after this all Strings add
Trie()
{
head = new TrieNode('\0');
ans = 0;
}
// Function to insert the Strings in
// the trie
void addWord(String s)
{
TrieNode temp = head;
int n = s.length();
for (int i = 0; i < n; i++)
{
// Inserting character-by-character
char ch = s.charAt(i);
// If the node of ch is not present in
// map make a new node and add in map
if (temp.children.get(ch) == null)
{
temp.children.put(ch, new TrieNode(ch));
}
temp = temp.children.get(ch);
temp.visited++;
}
}
// Recursive function to calculate the
// answer argument is passed by reference
int dfs(TrieNode node, int depth)
{
// To store changed visited values from
// children of this node i.e. number of
// nodes visited by its children
int vis = 0;
Iterator hmIterator = node.children.entrySet().iterator();
while (hmIterator.hasNext())
{
Map.Entry child = (Map.Entry)hmIterator.next();
vis += dfs((TrieNode)child.getValue(), depth + 1);
}
// Updating the visited variable, telling
// number of nodes that have
// already been visited by its children
node.visited -= vis;
int String_pair = 0;
// If node.visited > 1, means more than
// one String has prefix up till this node
// common in them
if (node.visited > 1)
{
// Number of String pair with current
// node common in them
String_pair = (node.visited / 2);
ans += (depth * String_pair);
// Updating visited variable of current node
node.visited -= (2 * String_pair);
}
// Returning the total number of nodes
// already visited that needs to be
// updated to previous node
return (2 * String_pair + vis);
}
// Function to run the dfs function for the
// first time and give the answer variable
int dfshelper()
{
// Stores the final answer
// as sum of all depths
ans = 0;
dfs(head, 0);
return ans;
}
}
// Driver code
public static void main(String args[])
{
Trie T = new Trie();
String str[]
= { "babab", "ababb", "abbab",
"aaaaa", "babaa", "babbb" };
int n = 6;
for (int i = 0; i < n; i++)
{
T.addWord(str[i]);
}
int ans = T.dfshelper();
System.out.println( ans );
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// Javascript program to find Sum of all LCP
// of maximum length by selecting
// any two Strings at a time
class TrieNode
{
// Initially visited value for all
// nodes is zero
constructor(x)
{
this.val = x;
// Counts the number of times the node
// is visited while making the trie
this.visited = 0;
// Using map to store the pointers
// of children nodes for dynamic
// implementation, for making the
// program space efficient
this.children = new Map();
}
}
class Trie
{
// Head node of the trie is initialize
// as '\0', after this all Strings add
constructor()
{
this.head = new TrieNode('\0');
this.ans = 0;
}
// Function to insert the Strings in
// the trie
addWord(s)
{
let temp = this.head;
let n = s.length;
for (let i = 0; i < n; i++)
{
// Inserting character-by-character
let ch = s[i];
// If the node of ch is not present in
// map make a new node and add in map
if (temp.children.get(ch) == null)
{
temp.children.set(ch, new TrieNode(ch));
}
temp = temp.children.get(ch);
temp.visited++;
}
}
// Recursive function to calculate the
// answer argument is passed by reference
dfs(node,depth)
{
// To store changed visited values from
// children of this node i.e. number of
// nodes visited by its children
let vis = 0;
for(let [key, value] of node.children.entries())
{
vis += this.dfs(value, depth + 1);
}
// Updating the visited variable, telling
// number of nodes that have
// already been visited by its children
node.visited -= vis;
let String_pair = 0;
// If node.visited > 1, means more than
// one String has prefix up till this node
// common in them
if (node.visited > 1)
{
// Number of String pair with current
// node common in them
String_pair = (node.visited / 2);
this.ans += (depth * String_pair);
// Updating visited variable of current node
node.visited -= (2 * String_pair);
}
// Returning the total number of nodes
// already visited that needs to be
// updated to previous node
return (2 * String_pair + vis);
}
// Function to run the dfs function for the
// first time and give the answer variable
dfshelper()
{
// Stores the final answer
// as sum of all depths
this.ans = 0;
this.dfs(this.head, 0);
return this.ans;
}
}
// Driver code
let T = new Trie();
let str
= [ "babab", "ababb", "abbab",
"aaaaa", "babaa", "babbb" ];
let n = 6;
for (let i = 0; i < n; i++)
{
T.addWord(str[i]);
}
let ans = T.dfshelper();
document.write( ans );
// This code is contributed by unknown2108
</script>
Producción:
6
Complejidad de tiempo:
para insertar todas las strings en el trie: O(MN)
Para realizar el recorrido de trie: O(26*M) ~ O(M)
Por lo tanto, la complejidad de tiempo general: O(M*N) , donde:
N = Number of strings M = Length of the largest string
Espacio Auxiliar: O(M)