A string S ∈ ∑~m can be viewed as a set of pairs S = {(σ_i, i) : i ∈ {0,..., m - 1}}. We consider approximate pattern matching problems arising from the setting where errors are introduced to the location component (i), rather than the more traditional setting, where errors are introduced into the content itself (σ_i). In this paper, we consider the case where bits of i may be erroneously flipped, either in a consistent or transient manner. We formally define the corresponding approximate pattern matching problems, and provide efficient algorithms for their resolution, while introducing some novel techniques.
展开▼
