A longest prefix lookup finds the longest stored key that prefixes an input string. It supports cases where the input itself is not stored, such as prefix-based spell checking. section 6.1.3 section 6.2.5
In a trie, follow the input characters while matching child edges. Track the path and the deepest key node encountered. If the path ends or a character is missing, return that key; recursive implementations find it while backtracking. The operation returns a string or null rather than a Boolean. section 6.2.5
The operation is exposed alongside ordinary container methods:
- insert(key), remove(key), and contains(key) manage stored strings. section 6.1.3
- longestPrefix(key) returns the longest stored prefix of the input. section 6.1.3
- keysStartingWith(prefix) retrieves every stored string sharing a prefix. section 6.1.3
Lookup procedure
Start at the trie root and consume characters from the searched string. Record each key node reached. When no matching edge remains, return the last recorded key node's string; if none was recorded, return null. section 6.2.5
Table 6.1 API and contract for StringContainer (view table figure)
Use the API contract to compare longestPrefix with insertion, removal, containment, and retrieval of all keys sharing a prefix. section 6.1.3
Listing 6.9 Method longestPrefix
function longestPrefix(node, s, prefix) #1
if s == “” then #2
if node.keyNode then #3
return prefix
else
return null #4
c, tail ← s.splitAt(0) #5
if node.children[c] == null then #6
if node.keyNode then return prefix else return null #7
else
result ← longestPrefix (node.children[c], tail, prefix + c) #8
if result != null then #9
return result
elsif node.keyNode then #10
return prefix
else
return null #11
Inspect the recursive pseudocode for stopping conditions, path tracking, child traversal, and backtracking. section 6.2.5
