dsa1 min read
Count Words Beginning with Prefix — Trie Count
Count words with given prefix. Simple trie with count at each node; reach prefix end and return count.
Read →
All Posts
1575 articles
dsa1 min read
Maximum XOR With an Element — Offline Trie
For each query (xi, mi), find max xi XOR with element ≤ mi. Offline: sort queries and elements by value, add elements up to mi, query trie.
Read →
dsa1 min read
Find Length of Longest Common Prefix — Digit Trie
Find the longest common prefix length between any number in arr1 and any number in arr2. Build trie from arr1 digits, query with arr2.
Read →
dsa2 min read
Trie Applications Overview — XOR, Autocomplete, Suffix
Overview of trie application variants: binary trie for XOR, reverse trie for suffix matching, counted trie for scoring, and offline trie processing.
Read →
dsa1 min read
Count Distinct Substrings — Suffix Trie / Rolling Hash
Count distinct substrings. Naive: insert all suffixes into trie and count nodes. Optimal: suffix automaton or rolling hash.
Read →
Page 175 of 315