• DocumentCode
    2026479
  • Title

    Common words between two random strings

  • Author

    Jacquet, P.

  • Author_Institution
    INRIA, Rocquencourt
  • fYear
    2007
  • fDate
    24-29 June 2007
  • Firstpage
    1481
  • Lastpage
    1485
  • Abstract
    We investigate the problem of enumerating the words that are common to two random strings. We show that when the source models are memoryless 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.
  • Keywords
    memoryless systems; random codes; source coding; string matching; trees (mathematics); common words; memoryless source model; random strings; suffix trees; Autocorrelation; Cats; Convergence; Dogs; Genetics; Information analysis; Information theory; Random number generation; Random sequences; Statistical analysis;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Information Theory, 2007. ISIT 2007. IEEE International Symposium on
  • Conference_Location
    Nice
  • Print_ISBN
    978-1-4244-1397-3
  • Type

    conf

  • DOI
    10.1109/ISIT.2007.4557431
  • Filename
    4557431
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2026479