next up previous contents index CD CD Algorithms
Next: Set Cover Up: A Catalog of Algorithmic Previous: Minkowski Sum

Set and String Problems


Sets and strings both represent collections of objects. The primary difference is whether order matters. Sets are collections of symbols whose order is assumed to carry no significance, while the arrangement of symbols is exactly what defines a string.   

The assumption of a canonical order makes it possible to solve string problems much more efficiently than set problems, through techniques such as dynamic programming and advanced data structures like suffix trees. The interest in and importance of string processing algorithms have been increasing, largely due to biological and text-processing applications. A product of this interest are three recent books on string algorithms:  

Mon Jun 2 23:33:50 EDT 1997