### Abstract

In this paper we describe a factorial language, denoted by L(S, k,r), that contains all words that occur in a string 5 up to k mismatches every r symbols. Then we give some combinatorial properties of a parameter, called repetition index and denoted by R(S,k,r), defined as the smallest integer h ? 1 such that all strings of this length occur at most in a unique position of the text S up to k mismatches every r symbols. We prove that R(S, k, r) is a non-increasing function of r and a non-decreasing function of k and that the equation r = R(S, k, r) admits a unique solution. The repetition index plays an important role in the construction of an indexing data structure based on a trie that represents the set of all factors of L(S,k,r) having length equal to R(S,k,r). For each word x ?L(S, k, r) this data structure allows us to find the list occ(x) of all occurrences of the word x in a text S up to k mismatches every r symbols in time proportional to |x| + |occ(x)|.

Lingua originale | English |
---|---|

Pagine | 224-235 |

Numero di pagine | 12 |

Stato di pubblicazione | Published - 2005 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Entra nei temi di ricerca di 'Languages with mismatches and an application to approximate indexing'. Insieme formano una fingerprint unica.

## Cita questo

Mignosi, F., Epifanio, C., & Gabriele, A. (2005).

*Languages with mismatches and an application to approximate indexing*. 224-235.