Skip to main content Skip to navigation

Algorithms on Strings

The area of algorithms on strings deals with one of the simplest and most fundamental data structures: a string (or sequence) of characters. Classical algorithmic problems on strings include exact pattern matching, string comparison, and approximate pattern matching. Algorithms on strings have numerous applications in different areas of science and technology, from simple text editors to sophisticated data mining and telecommunications. A particularly rich source of applications is computational molecular biology, where the role of strings is played by nucleotide sequences in a DNA molecule.

DIMAP members have contributed to research on string algorithms for several decades. These contributions include the fastest known algorithm for computing the edit distance between a pair of strings; several improvements to the classical Boyer--Moore exact pattern matching algorithm; efficient approximation of shortest common superstrings; efficient computation of string periods; efficient parallel algorithms for exact and approximate pattern matching problems in a number of parallel computation models.

The current research of DIMAP in the area of string algorithms is concerned with designing efficient algorithms for detailed string comparison and approximate pattern matching. Parts of this research are carried out in collaboration with Warwick Systems Biology Centre. We also investigate the communication requirements of parallel string comparison algorithms, and have recently designed the first parallel string comparison algorithm with scalable communication.

Sample publications: