Maxime Crochemore - Böcker

The book is intended for lectures on string processes and pattern matching in Master's courses of computer science and software engineering curricula. The details of algorithms are given with correctness proofs and complexity analysis, which make them ready to implement. Algorithms are described in a C-like language. The book is also a reference for students in computational linguistics or computational biology. It presents examples of questions related to the automatic processing of natural language, to the analysis of molecular sequences, and to the management of textual databases.

The book is intended for lectures on string processes and pattern matching in Master's courses of computer science and software engineering curricula. The details of algorithms are given with correctness proofs and complexity analysis, which make them ready to implement. Algorithms are described in a C-like language. The book is also a reference for students in computational linguistics or computational biology. It presents examples of questions related to the automatic processing of natural language, to the analysis of molecular sequences, and to the management of textual databases.

String matching is one of the oldest algorithmic techniques, yet still one of the most pervasive in computer science. The past 20 years have seen technological leaps in applications as diverse as information retrieval and compression. This copiously illustrated collection of puzzles and exercises in key areas of text algorithms and combinatorics on words offers graduate students and researchers a pleasant and direct way to learn and practice with advanced concepts. The problems are drawn from a large range of scientific publications, both classic and new. Building up from the basics, the book goes on to showcase problems in combinatorics on words (including Fibonacci or Thue-Morse words), pattern matching (including Knuth-Morris-Pratt and Boyer-Moore like algorithms), efficient text data structures (including suffix trees and suffix arrays), regularities in words (including periods and runs) and text compression (including Huffman, Lempel-Ziv and Burrows-Wheeler based methods).

String matching is one of the oldest algorithmic techniques, yet still one of the most pervasive in computer science. The past 20 years have seen technological leaps in applications as diverse as information retrieval and compression. This copiously illustrated collection of puzzles and exercises in key areas of text algorithms and combinatorics on words offers graduate students and researchers a pleasant and direct way to learn and practice with advanced concepts. The problems are drawn from a large range of scientific publications, both classic and new. Building up from the basics, the book goes on to showcase problems in combinatorics on words (including Fibonacci or Thue-Morse words), pattern matching (including Knuth-Morris-Pratt and Boyer-Moore like algorithms), efficient text data structures (including suffix trees and suffix arrays), regularities in words (including periods and runs) and text compression (including Huffman, Lempel-Ziv and Burrows-Wheeler based methods).

This book constitutes the proceedings of the 21st International Symposium on String Processing and Information Retrieval, SPIRE 2014, held in Ouro Preto, Brazil, in October 2014.

The 16th Annual Symposium on Combinatorial Pattern Matching was held on Jeju Island, Korea on June 19-22, 2005. Previous meetings were held in Paris, London, Tucson, Padova, Asilomar, Helsinki, Laguna Beach, Aarhus, Piscataway,Warwick,Montreal,Jerusalem,Fukuoka, Morelia,and Istanbul over the years 1990-2004. In response to the call for papers, CPM 2005 received a record number of 129papers.Eachsubmissionwasreviewedbyatleast threeProgramCommittee members with the assistance of external referees. Since there were many hi- quality papers, the Program Committee's task was extremely di?cult. Through an extensive discussion the Program Committee accepted 37 of the submissions tobepresentedattheconference.Theyconstituteoriginalresearchcontributions in combinatorial pattern matching and its applications. Inadditiontotheselectedpapers,CPM2005hadthreeinvitedpresentations, by Esko Ukkonen from the University of Helsinki, Ming Li from the University of Waterloo, and Naftali Tishby from The Hebrew University of Jerusalem.We would like to thank all Program Committee members and external r- erees for their excellent work, especially given the demanding time constraints; they gave the conference its distinctive character. We also thank all who s- mitted papers for consideration; they all contributed to the high quality of the conference. Finally, we thank the Organizing Committee members and the graduates- dents who worked hard to put in place the logistical arrangements of the c- ference. It is their dedicated contribution that made the conference possible and enjoyable.

The refereed proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, CPM 2003, held in Morelia, Michoacan, Mexico in June 2003. The 28 revised full papers presented were carefully reviewed and selected from 57 submissions. The papers are devoted to current theoretical and computational aspects of searching and matching strings and more complicated patterns, such as trees, regular expressions, graphs, point sets, and arrays. Among the application fields addressed are computational biology, bioinformatics, genomics, the Web, data compression, coding, multimedia, information retrieval, pattern recognition, and computer vision.

This volume contains the 22 papers accepted for presentationat the Third Annual Symposium on Combinatorial PatternMatching held April 29 to May 1, 1992, in Tucson, Arizona;it constitutes the first conference proceedings entirelydevoted to combinatorial pattern matching (CPM).CPM deals withissues of searching and matching of stringsand other more complicated patterns such as trees, regularexpressions, extended expressions, etc. in order to derivecombinatorial properties for such structures. As aninterdisciplinary field of growing interest, CPM is relatedto research in information retrieval, pattern recognition,compilers, data compression, and program analysis as well asto results, problems and methods from combinatorialmathematics and molecular biology.

The papers contained in this volume were presented at the 4th Annual Symposium on Combinatorial Pattern Matching, held in Padova, Italy, in June 1993. Combinatorial pattern matching addresses issues of searching and matching of strings and more complicated patterns such as trees, regular expressions and extended expressions. The goal is to derive non-trivial combinatorial properties for such structures and then to exploit these properties in order to achieve superior performance for the corresponding computational problems. The area is expected to grow further due to the increasing demand for speed and efficiency that comes especially from molecular biology and the Genome Project, but also from such diverse areas as information retrieval, pattern recognition, compilers, data compression and program analysis.

This volume presents the proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, held at Asilomar, California, in June 1994. The 26 selected papers in this volume are organized in chapters on alignments, various matchings, combinatorial aspects and bioinformatics. The contributors address such issues as the searching and matching of strings and more complicated patterns. The goal of the conference was to derive nontrivial combinatorial properties for such structures and then to exploit these properties in order to achieve superior performance for the corresponding computational problems.

The papers contained in this volume were presented at the Tenth Annual S- posium on Combinatorial Pattern Matching, held July 22 { 24, 1999 at the University of Warwick, England. They were selected from 26 abstracts subm- ted in response to the call for papers. In addition, invited lectures were given by JoanFeigenbaumfromAT&TLabsResearch(Massivegraphs:algorithms,app- cations, and open problems) and David Jones from the Department of Biology, University of Warwick (Optimizing biological sequences and protein structures using simulated annealing and genetic algorithms). The symposium was preceded by a two-day summer school set up to attract and train young researchers. The lecturers of the school were Alberto Ap- tolico (Computational Theories of Surprise), Joan Feigenbaum (Algorithmics of network-generatedmassivedatasets),Leszek Gasieniecand PaulGoldberg (The complexity of gene placement), David Jones (An introduction to computational molecularbiology), Arthur Lesk (Structuralalignmentandmaximalsubstructure extraction),Cenk Sahinalp(Questformeasuringdistancebetweenstrings:exact, approximate, and probabilistic algorithms), and Jim Storer.Combinatorial Pattern Matching (CPM) addresses issues of searching and matching strings and more complicated patterns such as trees, regular expr- sions, graphs, point sets, and arrays. The goal is to derive non-trivial combi- torial properties of such structures and to exploit these properties in order to achieve superior performance for the corresponding computational problems. Over recent years, a steady ?ow of high-quality research on this subject has changed a sparse set of isolated results into a fully-?edged area of algorithmics.

The term “stringology” is a popular nickname for text algorithms, or algorithms on strings. This book deals with the most basic algorithms in the area. Most of them can be viewed as “algorithmic jewels” and deserve reader-friendly presentation. One of the main aims of the book is to present several of the most celebrated algorithms in a simple way by omitting obscuring details and separating algorithmic structure from combinatorial theoretical background. The book reflects the relationships between applications of text-algorithmic techniques and the classification of algorithms according to the measures of complexity considered. The text can be viewed as a parade of algorithms in which the main purpose is to discuss the foundations of the algorithms and their interconnections. One can partition the algorithmic problems discussed into practical and theoretical problems. Certainly, string matching and data compression are in the former class, while most problems related to symmetries and repetitions in texts are in the latter. However, all the problems are interesting from an algorithmic point of view and enable the reader to appreciate the importance of combinatorics on words as a tool in the design of efficient text algorithms.In most textbooks on algorithms and data structures, the presentation of efficient algorithms on words is quite short as compared to issues in graph theory, sorting, searching, and some other areas. At the same time, there are many presentations of interesting algorithms on words accessible only in journals and in a form directed mainly at specialists. This book fills the gap in the book literature on algorithms on words, and brings together the many results presently dispersed in the masses of journal articles. The presentation is reader-friendly; many examples and about two hundred figures illustrate nicely the behaviour of otherwise very complex algorithms.