Patent ID: 8538999

Claim:
A computer-implemented method comprising: storing, by a computing device, a data structure with a tree form having at least two levels for storing two or more strings and at least one associated output string, wherein the data structure comprises at least one node at a first level of the tree form data structure having a field for storing a first substring of the two or more stored strings, at least three nodes at a second level of the tree form data structure respectively storing three substrings of the two or more stored strings, and at least three transitions, a match transition, a first fail transition, and a second fail transition, respectively governing transition from the one node at the first level to a first, a second and a third of the at least three nodes at the second level; receiving, by the computing device, a string; comparing, by the computing device, a first portion of the string to the substring of the one node of the first level; in response to the first portion of the string matching the substring of the one node of the first level, transitioning, by the computing device, from the one node of the first level, using the match transition, to the first node of the second level; in response to the first portion of the string not matching the substring of the one node of the first level, transitioning, by the computing device, from the one node of the first level, using a selected one of the first and second fail transitions, to a corresponding selected one of the second and third node of the second level.