{
  "id": "1803.03238",
  "version": "v1",
  "published": "2018-03-08T18:16:09.000Z",
  "updated": "2018-03-08T18:16:09.000Z",
  "title": "Length of the longest common subsequence between overlapping words",
  "authors": [
    "Boris Bukh",
    "Raymond Hogenson"
  ],
  "comment": "10 pages, 5 figures",
  "categories": [
    "math.PR"
  ],
  "abstract": "Given two random finite sequences from $[k]^n$ such that a prefix of the first sequence is a suffix of the second, we examine the length of their longest common subsequence. If $\\ell$ is the length of the overlap, we prove that the expected length of an LCS is approximately $\\max(\\ell, \\mathbb{E}[L_n])$, where $L_n$ is the length of an LCS between two independent random sequences. We also obtain tail bounds on this quantity.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-03-08T18:16:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05A05",
      "68R15"
    ],
    "keywords": [
      "longest common subsequence",
      "overlapping words",
      "independent random sequences",
      "random finite sequences",
      "first sequence"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}