A substring is handled as the portion of a search string still being matched. Trie search repeatedly separates that string into its first character and remaining tail, then follows the corresponding edge. section 6.2.2
Use substring matching in trie and radix-trie traversal as follows:
- If the remaining substring is empty, inspect the current node to determine whether the complete key is stored there. section 6.2.2
- Otherwise, compare its first character with outgoing edges and continue with the tail when a matching edge exists. section 6.2.2
- In a radix trie, compare the remaining substring with an edge label, which may match several characters or only a common prefix. section 6.3.1
Failed search
A search can fail when the next character has no outgoing edge, or when the substring is exhausted at an intermediate node that is not marked as storing a key. section 6.2.2
Figure 6.15 Possible cases comparing a search string to a node's links. (1) An edge’s label completely matches part of the string. (2) An edge’s label and the search string have a common prefix that is shorter than both strings. (3) The search string is a prefix of one of the edge’s labels. (4) The search string has no common prefix with any of the edges.
Compare the four radix-trie cases: complete edge-label matching, a shorter common prefix, the search string as an edge-label prefix, and no common prefix. section 6.3.1
