Quote: simple, fast algorithm for approximate string matching; special cases k-break periodic strings; uses suffix tree; short, overlapping text partitions; pattern at least 5k^3 where k is the maximum edit distance

Quotation Skeleton

We give two algorithms for finding all approximate … matching text substring is at most k. The … strings (defined later). The second algorithm runs in … time. … [p. 1762] By k-break periodic, we mean that there … pattern between these substrings (or breaks, as we … … [is] quite rare in practice. … [p. 1763] We assume that suffix trees for the … [refs]. We will assume that m, the pattern length, is at … algorithm is used for shorter patterns. … If the text is longer [than 2m-2k], then it …   Google-1   Google-2

Copyright clearance needed for quotation.

Related Topics

Topic: approximate string matching and pattern matching with errors (19 items)
Topic: suffix trie (18 items)