astructure that allows us to compute hashes of substrings in $O(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Hasher(object):\n",
    "    def __init__(self, word):\n",
    "        self.h = compute_hashes(word)\n",
    "        self.powers = compute_powers(len(word))\n",
    "        \n",
    "    def substring_hash(self, i, j):\n",
    "        result = self.h[j] - self.h[i] * self.powers[j-i]\n",
    "        return result % BIG_FAT_PRIME"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "TEXT = \"abcxabcx\"\n",
    "h = Hasher(TEXT)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ab]cxabcx 32\n",
      "abcx[ab]cx 32\n",
      "abc[xa]bcx 721\n"
     ]
    }
   ],
   "source": [
    "def highlight(word, i, j):\n",
    "    return word[:i] + \"[\" + word[i:j] + \"]\" + word[j:]\n",
    "\n",
    "print(highlight(TEXT, 0, 2), h.substring_hash(0, 2))\n",
    "print(highlight(TEXT, 4, 6), h.substring_hash(4, 6))\n",
    "print(highlight(TEXT, 3, 5), h.substring_hash(3, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hasher complexity analysis.\n",
    "\n",
    "Preprocessing (`__init__`):\n",
    "- `compute_hashes` is $O(n)$\n",
    "- 'compute_powers` is $O(n)$\n",
    "Therefore precomputing is $O(n)$.\n",
    "\n",
    "Queries (`substring_hash`) is of complexity $O(1)$ - it is just a simple formula."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that this technique is very powerful. More powerful than we need for pattern matching. It should not be a surprise that we can easily use it to solve pattern matching"
   ]
  },
  {
   "cell_type": "code",
   "execution_