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:  

• Crochemore and Rytter [CR94] - A comprehensive book on advanced string algorithms, but somewhat formal and fairly difficult to follow.
• Stephen [Ste94] - A reasonably gentle introduction to basic string algorithmics. Possibly the best available book for the beginner.
• Gusfield [Gus97] - This is now the most comprehesive introduction to string algorithms. It contains a thorough discussion on suffix trees, with new, clear formulations of classical exact string-matching algorithms.

• Set Cover
• Set Packing
• String Matching
• Approximate String Matching
• Text Compression
• Cryptography
• Finite State Machine Minimization
• Longest Common Substring
• Shortest Common Superstring