Common words between two random strings - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2006

Common words between two random strings

Philippe Jacquet

Résumé

We investigate the problem of enumerating the words that are common to two random strings. We show that when the source models are memoriless that the number of common words is sublinear in the length of the sequence, and linear when the source models are exactly the same. We draw the same conclusions for the number of common nodes in the associated respective suffix trees.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-5899.pdf (296.36 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00071368 , version 1 (23-05-2006)

Identifiants

  • HAL Id : inria-00071368 , version 1

Citer

Philippe Jacquet. Common words between two random strings. [Research Report] RR-5899, INRIA. 2006. ⟨inria-00071368⟩
63 Consultations
174 Téléchargements

Partager

Gmail Facebook X LinkedIn More