notebooks/CG_go_003_ZAlgorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "func z(s string) []int {\n",
    "    // Use Z-algorithm to preprocess given string.  See\n",
    "    // Gusfield for complete description of algorithm.\n",
    "    Z := make([]int, len(s)+1)\n",
    "    Z[0] = len(s)\n",
    "    \n",
    "    // Initial comparison of s[1:] with prefix\n",
    "    for i := 1; i < len(s); i++ {\n",
    "        if s[i] == s[i-1] {\n",
    "            Z[1] += 1\n",
    "        } else {\n",
    "            break\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    r, l := 0, 0\n",
    "    if Z[1] > 0 {\n",
    "        r, l = Z[1], 1\n",
    "    }\n",
    "    \n",
    "    for k := 2; k < len(s); k++ {\n",
    "        if k > r {\n",
    "            // Case 1\n",
    "            for i := k; i < len(s); i++ {\n",
    "                if s[i] == s[i-k] {\n",
    "                    Z[k] += 1\n",
    "                } else {\n",
    "                    break\n",
    "                }\n",
    "            }\n",
    "            r, l = k + Z[k] - 1, k\n",
    "        } else {\n",
    "            // Case 2\n",
    "            // Calculate length of beta\n",
    "            nbeta := r - k + 1\n",
    "            Zkp := Z[k - l]\n",
    "            if nbeta > Zkp {\n",
    "                // Case 2a: Zkp wins\n",
    "                Z[k] = Zkp\n",
    "            } else {\n",
    "                // Case 2b: Compare characters just past r\n",
    "                nmatch := 0\n",
    "                for i := r+1; i < len(s); i++ {\n",
    "                    if s[i] == s[i - k] {\n",
    "                        nmatch += 1\n",
    "                    } else {\n",
    "                        break\n",
    "                    }\n",
    "                }\n",
    "                l, r = k, r + nmatch\n",
    "                Z[k] = r - k + 1\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    return Z\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[11 0 0 1 0 1 0 4 0 0 1 0]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z(\"abracadabra\")\n",
    "// abracadabra (11)\n",
    "//    a        (1)\n",
    "//      a      (1)\n",
    "//        abra (4)\n",
    "//           a (1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5 4 3 2 1 0]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z(\"aaaaa\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "func zMatch(p, t string) []int {\n",
    "    s := p + \"$\" + t\n",
    "    Z := z(s)\n",
    "    occurrences := []int{}\n",
    "    for i := len(p) + 1; i < len(s); i++ {\n",
    "        if Z[i] >= len(p) {\n",
    "            occurrences = append(occurrences, i - (len(p) + 1))\n",
    "        }\n",
    "    }\n",
    "    return occurrences\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[9]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zMatch(\"needle\", \"haystack needle haystack\")\n",
    "//                012345678901234567890123\n",
    "//                          1         2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[9 16]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "zMatch(\"needle\", \"haystack needle needle\")\n",
    "//                0123456789012345678901\n",
    "//                          1         2"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Go",
   "language": "go",
   "name": "gophernotes"
  },
  "language_info": {
   "codemirror_mode": "",
   "file_extension": ".go",
   "mimetype": "",
   "name": "go",
   "nbconvert_exporter": "",
   "pygments_lexer": "",
   "version": "go1.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}