Approximate regular expression matching with multi-strings

摘要: In this paper, we are interested in solving the approximate regular expression matching problem: given a R advance and wish to answer following query: text T parameter k, find all substrings of which match with at most k errors (an error consist deleting inserting, or substituting character). There exists well known solution for problem time O(mn) where m is size (the number operators characters appearing R) n length text. also case k=0 (exact matching) solves O(dn), d strings (a string sequence connected concatenation operator). show that both methods can be combined solve O(kdn) arbitrary k. This bound much better than O(mn/log"k"+"2n) achieved by best actual algorithm