Implement approximate string matching algorithms

[krzysztof-turowski]

Approximate string matching with respect to the edit distance:

• Galil, Giancarlo - Improved String Matching with k Mismatches - requires also computation LCP(i, j) in $O(1)$ time from LCP i SA arrays e.g. using Fischer, Heun - Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Schoenmeyr, Yu Zhang - FFT-based algorithms for the string matching with mismatches problem
• Liu, Chen, James Borneman, Jiang - A Fast Algorithm for Approximate String Matching on Gene Sequences
• Salmela, Tarhio, Kalsi - Approximate Boyer-Moore String Matching for Small Alphabets (both Hamming and edit distance)

Approximate string matching with respect to the edit distance:

• Wu, Manber - Fast text searching: allowing errors
• Ukkonen - Finding Approximate Patterns in Strings
• Ukkonen, Wood - Approximate String Matching with Suffix Automata
• Baeza-Yates, Navarro - A faster algorithm for approximate string matching
• Myers - A fast bit-vector algorithm for approximate string matching based on dynamic programming
• Galil, Park - An improved algorithm for approximate string matching
• Chang, Lawler - Approximate String Matching in Sublinear Expected Time
• Landau, Vishkin - Fast String Matching with k Differences
• Landau, Viskin - Fast parallel and serial approximate string matching
• Cole, Hariharan - Approximate string matching: a simpler faster algorithm

Matching with wildcards:

• Fischer, Paterson - String-matching and other products
• Muthukrishnan, Palem - Non-standard Stringology: Algorithms and Complexity
• Indyk - Faster algorithms for string matching problems: matching the convolution bound
• Kalai - Efficient Pattern-Matching with Don't Cares