A Randomized Algorithm for Approximate String Matching.

Mikhail J. Atallah Frédéric Chyzak Philippe Dumas

Published in: Algorithmica (2001)

Keyphrases

approximate string matching
randomized algorithm
greedy algorithm
string matching
lower bound
edit distance
n gram
suffix array
indexing techniques
suffix tree
pattern matching
competitive ratio
pattern recognition
perceptron algorithm
upper bound
language model