{ "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 }