String Algorithms
Rod Stephens · 2019
String operations are common in many programs, so they have been studied extensively, and many programming libraries have good string tools. To understand the algorithms described for regular expression matching, it helps to understand deterministic finite automata and nondeterministic finite automata. This chapter describes deterministic and nondeterministic finite automata. It also explains how one can use them to perform pattern matching with regular expressions. The Boyer–Moore string search algorithm is a well-known algorithm that any student of algorithms should see at least once. Edit distance algorithms let one determines how close two words, strings, or even files are to each other and to find the differences between them. A phonetic algorithm is one that categorizes and manipulates words based on their pronunciation. The chapter also describes two phonetic algorithms: Soundex and Metaphone. Soundex and other phonetic algorithms are useful for finding names or other words when people are unsure of their spelling.