text processing trie for set of strings can be used to implement set or map whose keys are the strings of namelywe perform search in for string by tracing down from the root the path indicated by the characters in if this path can be traced and terminates at leaf nodethen we know is key in the map for examplein the trie in figure tracing the path for "bullends up at leaf if the path cannot be traced or the path can be traced but terminates at an internal nodethen is not key in the map in the example in figure the path for "betcannot be traced and the path for "beends at an internal node neither such word is in the map it is easy to see that the running time of the search for string of length is ( | |)because we visit at most nodes of and we spend (| |time at each node determining the child having the subsequent character as label the (| |upper bound on the time to locate child with given label is achievableeven if the children of node are unorderedsince there are at most |schildren we can improve the time spent at node to be (log | |or expected ( )by mapping characters to children using secondary search table or hash table at each nodeor by using direct lookup table of size |sat each nodeif |sis sufficiently small (as is the case for dna stringsfor these reasonswe typically expect search for string of length to run in (mtime from the discussion aboveit follows that we can use trie to perform special type of pattern matchingcalled word matchingwhere we want to determine whether given pattern matches one of the words of the text exactly word matching differs from standard pattern matching because the pattern cannot match an arbitrary substring of the text--only one of its words to accomplish thiseach word of the original document must be added to the trie (see figure simple extension of this scheme supports prefix-matching queries howeverarbitrary occurrences of the pattern in the text (for examplethe pattern is proper suffix of word or spans two wordscannot be efficiently performed to construct standard trie for set of stringswe can use an incremental algorithm that inserts the strings one at time recall the assumption that no string of is prefix of another string to insert string into the current trie we trace the path associated with in creating new chain of nodes to store the remaining characters of when we get stuck the running time to insert with length is similar to searchwith worst-case ( | |performanceor expected (mif using secondary hash tables at each node thusconstructing the entire trie for set takes expected (ntimewhere is the total length of the strings of there is potential space inefficiency in the standard trie that has prompted the development of the compressed triewhich is also known (for historical reasonsas the patricia trie namelythere are potentially lot of nodes in the standard trie that have only one childand the existence of such nodes is waste we discuss the compressed trie next