Suponga que hay una cola de n usuarios y su tarea es asignarles un nombre de usuario. El sistema funciona de la siguiente manera. Cada usuario tiene un inicio de sesión preferido en forma de una string ‘s’ que consiste solo en letras minúsculas y números. El nombre de usuario se asigna en el siguiente orden s, s0, s1, s2….s11…. significa que primero verifica s si s está disponible asígnelo si ya está ocupado verifique s0 si está libre asígnelo o si está ocupado verifique s1 y así sucesivamente… si se asigna un nombre de usuario a un usuario, se vuelve ocupado para otros usuarios detrás de él en la cola.
Ejemplos :
Entrada : nombres[] = {abc, bcd}
Salida : nombres_usuarios[] = {abc bcd}
Entrada : nombres[] = {abc, bcd, abc}
Salida : nombres_usuarios[] = {abc bcd abc0}
Entrada : nombres[] = {geek, geek0, geek1, geek}
Salida : user_names[] = {geek geek0 geek1 geek2}
Para el primer usuario, geek es gratuito, por lo que se le asigna de manera similar para el segundo y tercer usuario, pero para el cuarto usuario, geek no es gratuito, por lo que Verificaremos geek0 pero tampoco es gratis, luego buscaremos geek1 pero tampoco es gratis, luego verificaremos geek2 si es gratis, por lo que se le asigna.
Resolvemos este problema usando Trie . No usamos Trie habitual que tiene 26 hijos sino un Trie donde los Nodes tienen 36 hijos 26 alfabetos (az) y 10 números de (0-9). Además de esto, cada Node de Trie también tendrá una variable bool que se convertirá en verdadera cuando se inserte una string que termine en ese Node. También habrá una variable int, llamémosla agregar, que inicialmente será -1 y supongamos que la string es geek y esta variable int es igual a -1, entonces significa que devolveremos directamente geek como se solicita por primera vez, pero supongamos que es 12, entonces significa que string geek, geek0…..geek12 ya están presentes en el Trie .
Pasos
Paso 1: Mantenga un Trie como se discutió anteriormente.
Paso 2: para cada nombre dado, verifique si la string dada por el usuario no está en Trie, luego devuelva la misma string; de lo contrario, comience desde i = agregar + 1 (agregar se discute arriba) y comience a verificar si concatenamos i con la string de entrada está presente en el Trie o no, si no está presente, devuélvalo y establezca add=i e insértelo en Trie y, de lo contrario, incremente i Suponga que la
string es geek e i=5 verifique si geek5 está en Trie o no si no está presente return geek5 set add for geek = 5 inserte geek5 en Trie; de lo contrario, si no está presente, siga los mismos pasos para geek6 hasta que encuentre una string que no esté presente en Trie.
CPP
// C++ program to assign usernames to users
#include <bits/stdc++.h>
using namespace std;
#define MAX_CHAR 26
struct additional {
// is checks if the current node is
// leaf node or not
bool is;
// add counts number of concatenations
// of string are present in Trie
int add;
};
// represents Trie node
struct Trie {
// MAX_CHAR character children
Trie* character[MAX_CHAR];
// 10 numbers (from 0 to 9)
Trie* number[10];
// one additional struct children
additional a;
};
// function to get new node
Trie* getnew()
{
// initialising the Trie node
Trie* node = new Trie;
node->a.is = false;
node->a.add = -1;
for (int i = 0; i < MAX_CHAR; i++)
node->character[i] = NULL;
for (int i = 0; i < 10; i++)
node->number[i] = NULL;
return node;
}
// inserting a string into Trie
void insert(Trie*& head, string s)
{
Trie* curr = head;
for (int i = 0; i < s.length(); i++) {
if (s[i] - 'a' < 0) {
if (curr->number[s[i] - '0'] == NULL) {
curr->number[s[i] - '0'] = getnew();
}
curr = curr->number[s[i] - '0'];
}
else {
if (curr->character[s[i] - 'a'] == NULL)
curr->character[s[i] - 'a'] = getnew();
curr = curr->character[s[i] - 'a'];
}
}
curr->a.is = true;
}
// returns the structure additional
additional search(Trie* head, string s)
{
additional x;
x.is = false;
x.add = -1;
// if head is null directly return additional x
if (head == NULL)
return x;
Trie* curr = head;
// checking if string is present or not and
// accordingly returning x
for (int i = 0; i < s.size(); i++) {
if (s[i] - 'a' < 0) {
curr = curr->number[s[i] - '0'];
}
else
curr = curr->character[s[i] - 'a'];
if (curr == NULL)
return x;
}
x.is = curr->a.is;
x.add = curr->a.add;
return x;
}
// special function to update add variable to z
void update(Trie* head, string s, int z)
{
Trie* curr = head;
for (int i = 0; i < s.size(); i++) {
if (s[i] - 'a' < 0)
curr = curr->number[s[i] - '0'];
else
curr = curr->character[s[i] - 'a'];
}
curr->a.add = z;
}
void printUsernames(string username[], int n)
{
// Initialing a Trie root
Trie* head = getnew();
// Assigning usernames one by one
for (int i = 0; i < n; i++) {
string s = username[i];
additional x = search(head, s);
// if string is not present directly return it
if (x.is == false) {
cout << s << endl;
insert(head, s);
}
// to_string(x) converts integer x into string
else if (x.is == true) {
// start from x.add+1
int y = x.add + 1;
string x = s;
// continuing searching the string
// until a free username is found
while (1 < 2) {
// if free username is found
if (search(head, x + to_string(y)).is == false) {
// print it insert it and update add
cout << x << y << endl;
insert(head, x + to_string(y));
update(head, s, y);
break;
}
// else increment y
else if (search(head, x + to_string(y)).is == true)
y++;
}
}
}
}
// driver function
int main()
{
string name[] = { "geek", "geek0", "geek1", "geek" };
int n = sizeof(name) / sizeof(name[0]);
printUsernames(name, n);
return 0;
}
geek geek0 geek1 geek2