many network protocols , including the internet , have addresses that are structured hierarchically . the hierarchy is expressed by an address prefix p that represents all addresses in the given hierarchical level that starts with prefix p . the hierarchy is not strict and can be overridden by more inclusive hierarchies . this is achieved by having network routers find the longest prefix that matches a destination address in a message . the disclosed invention describes a method and apparatus for implementing controlled expansion : for expanding a set of prefixes into an equivalent set of prefixes that have a smaller set of prefix lengths . the new set of prefixes can then be looked up significantly faster using any technique whose speed improves by reducing the number of prefix lengths . our invention also incorporates fast techniques to insert and delete new prefixes , and a technique of pointer hoisting to halve the memory reads needed for trie search . our solution to longest matching prefix also applies to other routing protocols such as osi routing , call routing in telephone networks , and to string matching problems .