As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [trie]

A tree-like data structure used to hold an associative array, also called a Prefix Tree.

Filter by
Sorted by
Tagged with
0 votes
0 answers
25 views

Find string match among a large list of (prefix, suffix) pairs [closed]

Consider a large list of (prefix, suffix) string pairs. For each pair, len(prefix)+len(suffix) doesn't exceed L (21 in practice). We will be getting many query strings that can be answered in batches ...
Serge Rogatch's user avatar
2 votes
1 answer
46 views

CS50 Trie Week 5: check function not working

I have been trying to complete the trie practice problem from the CS50 course. The check function that I wrote must check whether the user input is found within the trie that has been created in the ...
thombellll's user avatar
-1 votes
0 answers
30 views

Finding Compound Words in A Text File Using A Trie in the Fast Amount of Time

I want to find all of the compound words in my text file in the fastest amount of time. I have completed my code so that my trie works and all 173,000 words get entered into the trie, but I'm not sure ...
G T's user avatar
  • 29
1 vote
0 answers
54 views

Finding Compound Words in A Text File of 150,000+ Words [closed]

I have to find all of the compound words in a text file. This file contains almost 200,000 words and I am trying to implement this in the least amount of time. So for example, the text file contains ...
G T's user avatar
  • 29
0 votes
1 answer
63 views

How does this code work and not crash or seg fault?

So this question is a bit different, the code works I just don't know why or how. I'm taking the CS50 course and I'm solving this practice problem aiming at training us at searching tries databases. ...
user75470's user avatar
0 votes
0 answers
32 views

Indexing JSON Commands with a tree model of GTK+ GUI

I have an idea that I want to implement but have no idea on how to proceed or an algorithm for that. I have a json file that has a list of strings as commands In the Client Side of the GUI, I use GTK+...
andre_lamothe's user avatar
0 votes
0 answers
51 views

What's the fastest way for Longest Prefix Match algorithm?

I am looking for an algorithm that does a fast lookup on the longest prefix match that can be used to match an input number(between 6 and 16 digits long) to a large set of prefixes (about 200k entries)...
Dave Greeko's user avatar
0 votes
0 answers
43 views

When implementing Trie Data Structure using smart pointer is it necessary to use shared pointers?

Link to gfg: Trie Data Structure using smart pointer I came across this implementation of Trie Data Structure using shared pointers. But I don't understand the purpose of using shared pointers. Can we ...
Ojas Bhamare's user avatar
0 votes
1 answer
53 views

NULL values are being reassigned to garbage at runtime

I have a C program to implement of Trie in which each not stores some data (see below). The trie should use strings in it's branches to arrange data (ie as keys) with integer data at each terminating ...
Dace's user avatar
  • 9
0 votes
1 answer
27 views

Unexpected error in Trie delete string method

I am trying to build a method to delete a string from Trie , when i run the code it says the following error despite the fact that everything is correct ( according to me ) whats the error in my code ...
Vivek084's user avatar
-2 votes
1 answer
89 views

Maximum XOR with all possible subsets of an array with a specific integer

Given an array of integers P = [P1, P2, ...] and a function F(M) that returns the XOR of all integers present in set M. If M is empty, then F(M) = 0. The task is to find the maximum possible value of ...
Niul Panvalkar's user avatar
1 vote
1 answer
34 views

Is there an existing Data Structure like this? ( A modified Trie )

I have been working on trie data structure recently and an alternative immediately struck to me. For example : This is a trie with 2 words : football and goofball. This is the alternate data structure ...
Saksham's user avatar
  • 11
0 votes
0 answers
60 views

How to use marisa-trie in Python for nlp processing

I'm working for a NLP function to store tokens in a trie. This my well working code for tokenization: import spacy def preprocess_text_spacy(text): stop_words = ["a", "the",...
Lilly_Co's user avatar
  • 159
2 votes
1 answer
74 views

How to create slice of LPM trie record for IPs/CIDRs

I am trying to use the BatchUpdate and BatchDelete API from https://github.com/cilium/ebpf/blob/master/map.go#L952-L1038. from my understanding, I need to create slice of LPM trie of IPs/CIRDs, for ...
99Linux's user avatar
  • 166
0 votes
1 answer
37 views

How to iterate over each word in a Trie using __iter__()and __next__() functions and generators in Python

I have a Trie that is structured below. I am trying to write an iterator and next function that will iterate over each word in the Trie and then raise StopIteration once it is completed but I'm ...
user3308817's user avatar
0 votes
0 answers
19 views

Trie class method is not working in search auto complete

I Am triyng to autocomplete and also want pass category as parameter in url. I have two table 1. First table name product_search_history and it has column id,catuid, search_term, search_date,status 2. ...
Emanuela's user avatar
-1 votes
1 answer
47 views

c++: segmentation fault for Trie data structure [closed]

I am a noobie to c++ and I'm recently learning trie data structure. As I was implementing the header file for the Trie, I've encountered segmentation fault that I cannot resolve. I used the typical ...
ayoMax00379's user avatar
0 votes
0 answers
61 views

How to calculate the time complexity for Leetcode's Longest Common Prefix with a solution using Tries

I am trying to improve my problem solving skills, and have solved problem #14 in Leetcode "Longest Common Prefix" using the Trie data structure. My solution runs in 106ms and beats 42.91%. ...
iamhaitham's user avatar
0 votes
0 answers
20 views

How to split the sentence where there is no space between in the sentence

How Google splits the sentence entered on the Google search bar into meaningful words For example Whatispython? Into What is python? Which algorithm to use for splitting the sentence to meaningful ...
Deku sukuna's user avatar
0 votes
3 answers
73 views

Python Trie implementation - Inserting elements into a trie recursively

I have implemented a trie tree using a list in Python which stores words. I am trying to write a function that insert words into a trie recursively. Here my trie class and the function insert() : ...
Nielwig's user avatar
  • 81
0 votes
0 answers
25 views

How to implement/ deploy a TRIE made with Python?

I have created a TRIE based structure for a search algorithm for the company I work for, and each node in the TRIE stores some data related to the product it maps to, for example, a node (when ...
Prateek Jain's user avatar
0 votes
0 answers
20 views

How to solve this ==31==error Address sanitizer heap buffer overflow error?

/** * Note: The returned array must be malloced, assume caller calls free(). */ char memo[10]; int count[500]={0,}; typedef struct Trie{ int count; struct Trie * next[26]; }Trie; void ...
이학명's user avatar
0 votes
1 answer
62 views

Is there an alternative to Trie for my needs?

I have a program that requires an ID to load a template. The template is assigned based on the ID. Each template has a key, e.g. tx. IDs that contain this pattern will have this template assigned, e.g ...
user20395797's user avatar
0 votes
0 answers
204 views

How do I implement a memory arena allocator to reduce memory request calls in a trie-based spell checker?

As part of the cs50x course, I made a trie-based dictionary spell checker that passes all of check50's tests as well as valgrind so no memory errors. Now I'm trying to implement a memory bucket to ...
Jordan Chen's user avatar
0 votes
1 answer
47 views

why the pointer is not incrementing at line 27

i am implementing the trie data structure, why my pointer is not incrementing at line# 27. all the characters are getting into forst node only. this is my code class Trienode: data:str next:...
Mohammad Avesh Husain's user avatar
1 vote
1 answer
177 views

Why isn't bitwise trie a popular implementation of associative array

I have to store billions of entries with Int64 keys in an ordered map. If I use a usual BST then each search operation costs log(N) pointer dereferencings (20-30 for millions to billions entries), ...
Andrey Godyaev's user avatar
0 votes
0 answers
118 views

How to specify a lifetime for a borrow in a struct in Rust?

I have a Trie struct whose nodes have children which are also nodes: pub struct Trie<'a, T: marker::Copy> { nodes: [Option<TrieNode<'a, T>>; MAX_NODE_LEN], min_len: usize, ...
Basil's user avatar
  • 428
1 vote
0 answers
36 views

How would a patricia tree look like after adding a word that starts as the substring of another but has additional letters?

Take this trie as example: I want to add the word "luan" to this representation, but luan takes 20 bits to represent, while lua takes 15. So, they "differ" from each other on the ...
Jonas's user avatar
  • 392
0 votes
1 answer
19 views

Unset element from trie using reference

I am having some difficulties to delete empty parent node if empty from a trie. I can correctly identify the node that has the value 3, but then I cannot unset nodes that do not have any children. ...
Razorphyn's user avatar
  • 1,314
0 votes
0 answers
64 views

Which products or database use Trie data structure and for what purposes?

Wanted to understand the usage of Trie data structure. I have seen that for Type ahead suggestions Trie is good. My understanding was that for distributed searching as well Trie is used. But I learnt ...
pranjal chugh's user avatar
0 votes
0 answers
14 views

Data structure to store, update and search very large size of Gazetteers?

I have a set of Gazetteer which contains tens of millions of entities, and I need that to do entity spotting in texts, and the Gazetteer set would be updated if necessary. Is compressed trie the best ...
Lerner Zhang's user avatar
  • 5,996
0 votes
2 answers
131 views

Algorithm to find all duplicate sequences of tokens in a long string

Let's say I have a really long string consists of 10^6 tokens (for simplicity, token is a space-separated word, so this string is splitted to list of tokens) now I need to find all possible duplicated ...
Izik's user avatar
  • 706
0 votes
0 answers
62 views

Longest Common Substring from Trie

i'm trying to obtain the longest common substring from two strings and have coded a trie, but im not too sure how to obtain the longest common substring based on this trie. Could someone please help, ...
marvel's user avatar
  • 1
-1 votes
1 answer
32 views

why my code doesn't change the head value in c# or i have to use somethings like pointers?

ok, guys, so I was doing the ReplaceWord problems from leetcode in c# ! and I had to initialize a prefix tree. the reason why I use c# that because it has split method which c++ doesn't have.the ...
Masterdemon123's user avatar
0 votes
0 answers
50 views

Handle and search large json file (android)

I have a json file that have a large (~200K) data set (non-complex objects with 4 fields). I should do prefix search for some of its field. There wont be any retrofit/api call, pagination stuff, or ...
drumess's user avatar
  • 37
0 votes
1 answer
27 views

Why are the Trie Functions unable to produce my desired output?

Your task is to create a trie system that is hosted online with a global state that supports multiple concurrent clients and the following operations: Add keyword to trie Delete a keyword from trie ...
Lexus9Power's user avatar
0 votes
1 answer
41 views

What is the problem with fill() here ? I used normal for loop for assigning NULL and it worked , with fill() it was giving error

The code below is a Trie implementation in C++. Kindly checkout what is the problem in using fill(). And if any suggestions improving my implementation are welcome Commented fill() in the TrieNode ...
Manu's user avatar
  • 13
0 votes
2 answers
122 views

How to return an int within a trie in python

I'm trying to search for a word within my trie data structure and if it exists in the trie, return the word and its frequency. This is what the trie looks like: {'c': {'u': {'t': {('e', 10): True, ('s'...
fnct's user avatar
  • 9
-1 votes
5 answers
278 views

how to write a function that returns all elements with same attribute from domtree?

I saw somewhere that this question was asked in a faang interview and I cannot come up with an optimized solution or find it anywhere. So the question basically wants us to write a function that ...
seyet's user avatar
  • 1,060
1 vote
0 answers
151 views

Difference between a patricia trie (radix tree with r = 2) and a binary trie?

I am trying to consolidate my understanding of the difference between a patricia trie (radix tree with r = 2) and a binary trie. As far as I can see the implementation of a binary trie and a patricia ...
markodeezy's user avatar
0 votes
0 answers
75 views

How to add callback function in Tries (prefix Tree) python

I am wondering how to implement callback function (watch) based on current function in prefix tree path is a / separated string describing the node. Example /animals/dogs/german_shepard. Values are ...
xxxYYYzzz's user avatar
-1 votes
2 answers
69 views

What is wrong with my trie suggestion algorithm?

I am coding an algorithm that uses the trie data structure. Basically, if input is "he", it will return ["hello","help","held","hen",...
dfmaaa1's user avatar
  • 67
0 votes
1 answer
57 views

Leetcode Testing of Trie Results Don't Match Local NodeJs Output

Description: I implemented a [Trie on Leetcode][1] and when I test it locally, running Node v16.15.1, the output of the test case I get does not match the output on LeetCode. I ran the initial test ...
BJ Rutledge's user avatar
0 votes
0 answers
33 views

Listing suggestions in a phonebook

Implement a phonebook where you can insert a contact, search for a contact, also provide suggestions based on user's input The insertion and search can be done using a simple hashmap. This is a ...
pensee's user avatar
  • 337
-3 votes
1 answer
244 views

How do I implement code to search word in a Trie?

Code: Search word in Trie Implement the function SearchWord for the Trie class. For a Trie, write the function for searching a word. Return true if the word is found successfully, otherwise return ...
Satyam Lal's user avatar
0 votes
1 answer
83 views

How to paginate a trie, so you can find 100 words matching prefix in the trie, starting at a paginated offset?

I am using a trie made to work on alphabets/scripts from any language. class TrieNode { constructor(key) { // the "key" value will be the character in sequence this.key = key; ...
Lance's user avatar
  • 74.4k
1 vote
2 answers
137 views

How to find all words that "contain" or "unscramble" an input string using a Trie?

Here is a trie made to work on alphabets/scripts from any language. class TrieNode { constructor(key) { // the "key" value will be the character in sequence this.key = key; // ...
Lance's user avatar
  • 74.4k
-2 votes
1 answer
326 views

Design In-Memory File System - Python - Trie - Leetcode Error

I am trying to solve the below leetcode problem Design a data structure that simulates an in-memory file system. Implement the FileSystem class: FileSystem() Initializes the object of the system. List ...
young_coder's user avatar
0 votes
1 answer
129 views

Get words from trie containing specific letters

I'd like to retrieve words from a trie that contain specific letters. For example: List all words that contain the letters [a, g]. If my trie has the words ["APPLE", "EGG", "...
Brati's user avatar
  • 1
1 vote
1 answer
94 views

Trie is Using Too Much Memory

I'm trying to get all the words made from the letters, 'crbtfopkgevyqdzsh' from a file called web2.txt. The posted cell below follows a block of code which improperly returned the whole run up to a ...
peoplet's user avatar
  • 81

1
2 3 4 5
23