Thomas Mailund - Efficient Text Representation and Search

Any source code or other supplementary material referenced by the author in this book is available to readers on GitHub via the books product page, located at www.apress.com/9781484259191 . For more detailed information, please visit http://www.apress.com/source-code .

Algorithms operating on strings are fundamental to many computer programs, and in particular searching for one string in another is the core of many algorithms. An example is searching for a word in a text document, where we want to know everywhere it occurs. This search can be exact, meaning that we are looking for the positions where the word occurs verbatim, or approximative, where we allow for some spelling mistakes.

This book will teach you fundamental algorithms and data structures for exact and approximative search. The goal of the book is not to cover the theory behind the material in great detail. However, we will see theoretical considerations where relevant. The purpose of the book is to give you examples of how the algorithms can be implemented. For every algorithm and data structure in the book, I will present working C code and nowhere will I use pseudocode. When I argue for the correctness and running time of algorithms, I do so intentionally informal. I aim at giving you an idea about why the algorithms solve a specific problem in a given time, but I will not mathematically prove so.

You can copy all the algorithms and data structures in this book from the pages, but they are also available in a library on GitHub: https://github.com/mailund/stralg . You can download and link against the library or copy snippets of code into your own projects. On GitHub you can also find all the programs I have used for time measurement experiments so you can compare the algorithms performance on your own machine and in your own runtime environment.

Unless otherwise stated , we use x, y, and p to refer to strings and i, j, k, l, and h to denote indices. We use to denote the empty string. We use a, b, and c for single characters. As in C, we do not distinguish between strings and pointers to a sequence of characters. Since the book is about algorithms in C, the notation we use matches that which is used for strings, pointers, and arrays in C. Arrays and strings are indexed from zero, that is, A[0] is the first value in array A (and x[0] is the first character in string x). The ith character in a string is at index i 1.

When we refer to a substring, we define it using two indices, i and j, ij, and we write x[i, j] for the substring. The first index is included and the second is not, that is, x[i, j] = x[i]x[i + 1] x[ j 1]. If a string has length n, then the substring x[0, n] is the full string. If we have a character a and a string x, then ax denotes the string that has a as its first character and is then followed by the string x. We use ak to denote a sequence of as of length k. The string a3x has a as its first three characters and is then followed by x. A substring that starts at index 0,