String Algorithms in C: Efficient Text Representation and Search

© Thomas Mailund 2020

T. MailundString Algorithms in Chttps://doi.org/10.1007/978-1-4842-5920-7_2

2. Classical algorithms for exact search

Thomas Mailund¹ 

(1)

Aarhus N, Denmark

 

We kick the book off by looking at classical algorithms for exact search, that is, finding positions in a string where a pattern string matches precisely. This problem is so fundamental that it received much attention in the very early days of computing, and by now, there are tens if not hundreds of approaches. In this chapter, we see a few classics.

Recall that we use iterators whenever we have an algorithm that loops over results that should be reported. All iterators must be initialized, and the resources they hold must be deallocated when we no longer need the iterator. ...