e": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "'A' 65\n",
      "'a' 97\n",
      "'b' 98\n",
      "'c' 99\n",
      "' ' 32\n",
      "'c' - 'a' + 1 = 3\n"
     ]
    }
   ],
   "source": [
    "# we need to map letters to numbers. Python function ord does the job\n",
    "print(repr('A'), ord('A'))\n",
    "print(repr('a'), ord('a'))\n",
    "print(repr('b'), ord('b'))\n",
    "print(repr('c'), ord('c'))\n",
    "print(repr(' '), ord(' '))\n",
    "\n",
    "print('%s - %s + 1 = %d' % (repr('c'), repr('a'), ord('c') - ord('a') + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "BIG_FAT_PRIME = 2**32 - 1\n",
    "ENGLISH_BASE = 30 # in theory 27 is sufficient but better safe than sorry!\n",
    "\n",
    "def compute_hashes(text, base=ENGLISH_BASE, modulo = BIG_FAT_PRIME):\n",
    "    # \n",
    "    h = [None for _ in range(len(text) + 1)]\n",
    "    h[0] = 0 # hash of empty word is 0\n",
    "    for i in range(len(text)):\n",
    "        # we only deal with english letters so we subtract 'a'\n",
    "        # to normalize range. We add 0 to avoid creating zero digit.\n",
    "        letter_as_number = (ord(text[i]) - ord('a') + 1)\n",
    "        h[i + 1] = h[i] * base + letter_as_number\n",
    "        h[i + 1] %= modulo\n",
    "        # at the end of the iteration h[i+1] is the hash\n",
    "        # of prefix of text of lenght (i+1) which in\n",
    "        # Python is text[:(i+1)]\n",
    "    return h"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "PROTIP: If you happen to ever implemented this is lower level programming language like C or C++, be ware of integer overflows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
     