 "text/plain": [
       "[0, 2, 61, 1832, 54961, 1648833, 49464992]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_hashes(\"babacb\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 61, 1832, 54964, 1648924, 49467724]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_hashes(\"babddd\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0,\n",
       " 2,\n",
       " 61,\n",
       " 1832,\n",
       " 54964,\n",
       " 1648924,\n",
       " 49467721,\n",
       " 1484031649,\n",
       " 1571276524,\n",
       " 4188622771,\n",
       " 1104631594,\n",
       " 3074176759,\n",
       " 2030989594,\n",
       " 800145691,\n",
       " 2529534259]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# for longer strings modulo matters\n",
    "compute_hashes(\"babddasdasdsad\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## hashes of substrings\n",
    "\n",
    "Now here's a crutial observation. Let's take polynomial representation of string  $babacb$ (where $X$ is the base)\n",
    "\n",
    "$$\n",
    "b*X^5 + a * X^4 + b*X^3 + a*X^2 + c*X^1 + b*X^0 \n",
    "$$\n",
    "\n",
    "Say we want to compute hash of $ac$ which is conveniently appears on 4-th index the string we originally hashed. Moreover we have hashes of all the prefixes - it seems like we are in good shape:\n",
    "\n",
    "\\begin{align}\n",
    "\\text{we have }\\ \\ \\ & hash(babac) &=\\ & b*X^4 + a * X^3 + b*X^2 &+& a*X^1 + c*X^0 \\\\\n",
    "\\text{we have }\\ \\ \\  & has