Review of some basic concepts on complexity, data structures and
algorithms.
Exact pattern recognition. The brute-fore algorithm. Algorithms
based on preprocessing. Preprocessing in linear time. Linear-time exact
matching algorithm.
The Boyer-Moore algorithm. Analysis of their complexity. The
Knuth-Morris-Pratt algorithm. Pattern recognition with finite automata.
Real-time string matching.
Preprocessing in the Knuth-Morris-Pratt algorithm. Exact matching
with a set of patterns.
The edit distance between two strings. Dynamic programming
calculation of edit distance. String similarity.
Introduction to sufix trees. The naive algorithm to build sufix
trees. Ukkonen’s linear-time suffix tree algorithm. Practical
implementation issues.
Aplications of exact string pattern recognition algorithms. Suffix
trees and the exact set matching problem. The substring of more than
two strings. Longest common substring of two strings. DNA
contamination. Circular string linearization. The edit distance and the
problem of melodic similarity.