h(bab)   &=\\ & b*X^2 + a * X^1 + b*X^0&&\\\\\n",
    "\\text{we WANT }\\ \\ \\  & hash(ac)    &=\\ &                         && a*X^1 + c*X^0\\\\\n",
    "\\end{align}\n",
    "\n",
    "\n",
    "From above we can clearly see that:\n",
    "\n",
    "$$\n",
    "hash(ac) = hash(babac) - X^2 * hash(bab)\n",
    "$$\n",
    "\n",
    "We can generalize this to arbitrary substring of our hashed string. Assume we hashed string $s_0, s_1, ..., s_{n-1}$ such that $h_0 = hash(\\emptyset)$, $h_1 = hash(s_0)$, $h_2 = hash(s_0, s_1)$ etc. \n",
    "Then we can compute $hash(s_i, ..., s_j)$ using the following formula:\n",
    "\n",
    "$$\n",
    "hash(s_i, ..., s_{j-1}) = h_j - h_i * X ^{j - i}\n",
    "$$\n",
    "\n",
    "This looks very close to $O(1)$ complexity hash computation if not for $X ^{j - i}$. But since there are at most $n$ different powers of $X$ that we are interested in, we can precompute them in $O(n)$ time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compute_powers(n, base=ENGLISH_BASE, modulo=BIG_FAT_PRIME):\n",
    "    powers = [None for _ in range(n + 1)]\n",
    "    powers[0] = 1\n",
    "    for i in range(n):\n",
    "        powers[i+1] = (powers[i] * base) % modulo\n",
    "    return powers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,\n",
       " 30,\n",
       " 900,\n",
       " 27000,\n",
       " 810000,\n",
       " 24300000,\n",
       " 729000000,\n",
       " 395163525,\n",
       " 3264971160,\n",
       " 3459854310,\n",
       " 716414220]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_powers(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can put all those observations together into efficient det