Affordable Access

Common words between two random strings

Authors
  • Jacquet, Philippe
Publication Date
Jan 01, 2006
Source
HAL
Keywords
Language
English
License
Unknown
External links

Abstract

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.

Report this publication

Statistics

Seen <100 times