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