)]}'
{
  "log": [
    {
      "commit": "df3fb93ad9ec0b20c785c0ad82d42d159a1af272",
      "tree": "e29ba25f55cb77e24310999a949b433e98d7656e",
      "parents": [
        "2de4ff7bd658c97fb357efa3095a509674dacb5a"
      ],
      "author": {
        "name": "Thomas Graf",
        "email": "tgraf@suug.ch",
        "time": "Thu Jun 23 20:58:37 2005 -0700"
      },
      "committer": {
        "name": "David S. Miller",
        "email": "davem@davemloft.net",
        "time": "Thu Jun 23 20:58:37 2005 -0700"
      },
      "message": "[LIB]: Knuth-Morris-Pratt textsearch algorithm\n\nImplements a linear-time string-matching algorithm due to Knuth,\nMorris, and Pratt [1]. Their algorithm avoids the explicit\ncomputation of the transition function DELTA altogether. Its\nmatching time is O(n), for n being length(text), using just an\nauxiliary function PI[1..m], for m being length(pattern),\nprecomputed from the pattern in time O(m). The array PI allows\nthe transition function DELTA to be computed efficiently\n\"on the fly\" as needed. Roughly speaking, for any state\n\"q\" \u003d 0,1,...,m and any character \"a\" in SIGMA, the value\nPI[\"q\"] contains the information that is independent of \"a\" and\nis needed to compute DELTA(\"q\", \"a\") [2]. Since the array PI\nhas only m entries, whereas DELTA has O(m|SIGMA|) entries, we\nsave a factor of |SIGMA| in the preprocessing time by computing\nPI rather than DELTA.\n \n[1] Cormen, Leiserson, Rivest, Stein\n    Introdcution to Algorithms, 2nd Edition, MIT Press\n[2] See finite automation theory\n\nSigned-off-by: Thomas Graf \u003ctgraf@suug.ch\u003e\nSigned-off-by: David S. Miller \u003cdavem@davemloft.net\u003e\n"
    }
  ]
}