Efficient Algorithms for Pattern Matching with General Gaps and Character Classes

摘要

We develop efficient dynamic programming algorithms for a pattern matching with general gaps and character classes. We consider patterns of the form p_0g(a_0, b_0)p_1g(a_1, b_1)…-p_m-1, where p_i is contained in ∑, where ∑ is some finite alphabet, and g(a_i, b_i) denotes a gap of length a_i... b_i between symbols p_i and p_(i+1). The text symbol t_j matches p_i iff t_j ∈ p_i. Moreover, we require that if p_i matches t_j, then P_(i+1) should match one of the text symbols t_(j+a_i+1)…t_(j+b_i+1). Either or both of a, and b_i can be negative. We give algorithms that have efficient average and worst case running times. The algorithms have important applications in music information retrieval and computational biology. We give experimental results showing that the algorithms work well in practice.