tries the pattern-matching algorithms presented in section speed up the search in text by preprocessing the pattern (to compute the failure function in the knuthmorris-pratt algorithm or the last function in the boyer-moore algorithmin this sectionwe take complementary approachnamelywe present string searching algorithms that preprocess the text this approach is suitable for applications where series of queries is performed on fixed textso that the initial cost of preprocessing the text is compensated by speedup in each subsequent query (for examplea web site that offers pattern matching in shakespeare' hamlet or search engine that offers web pages on the hamlet topica trie (pronounced "try"is tree-based data structure for storing strings in order to support fast pattern matching the main application for tries is in information retrieval indeedthe name "triecomes from the word "retrieval in an information retrieval applicationsuch as search for certain dna sequence in genomic databasewe are given collection of stringsall defined using the same alphabet the primary query operations that tries support are pattern matching and prefix matching the latter operation involves being given string and looking for all the strings in that contain as prefix standard tries let be set of strings from alphabet such that no string in is prefix of another string standard trie for is an ordered tree with the following properties (see figure )each node of except the rootis labeled with character of the children of an internal node of have distinct labels has leaveseach associated with string of ssuch that the concatenation of the labels of the nodes on the path from the root to leaf of yields the string of associated with thusa trie represents the strings of with paths from the root to the leaves of note the importance of assuming that no string in is prefix of another string this ensures that each string of is uniquely associated with leaf of (this is similar to the restriction for prefix codes with huffman codingas described in section we can always satisfy this assumption by adding special character that is not in the original alphabet at the end of each string an internal node in standard trie can have anywhere between and |schildren there is an edge going from the root to one of its children for each character that is first in some string in the collection in additiona path from the root of to an internal node at depth corresponds to -character prefix [ :