Chapter_32_String_Matching/exercises_32.4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 32.4 The Knuth-Morris-Pratt algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.4-1\n",
    "\n",
    "> Compute the prefix function $\\pi$ for the pattern $\\text{ababbabbabbababbabb}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\pi = \\{ 0, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 3, 4, 5, 6, 7, 8 \\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.4-2\n",
    "\n",
    "> Give an upper bound on the size of $\\pi^*[q]$ as a function of $q$. Give an example to show that your bound is tight."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\left | \\pi^*[q] \\right | < q$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.4-3\n",
    "\n",
    "> Explain how to determine the occurrences of pattern $P$ in the text $T$ by examining the $\\pi$ function for the string $PT$ (the string of length $m+n$ that is the concatenation of $P$ and $T$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\{ q ~|~ \\pi[q] = m ~\\text{and}~ q \\ge 2m \\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.4-4\n",
    "\n",
    "> Use an aggregate analysis to show that the running time of KMP-MATCHER is $\\Theta$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The number of $q = q + 1$ is at most $n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.4-5\n",
    "\n",
    "> Use a potential function to show that the running time of KMP-MATCHER is $\\Theta(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Phi = p$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.4-6\n",
    "\n",
    "> Show how to improve KMP-MATCHER by replacing the occurrence of $\\pi$ in line 7 (but not line 12) by $\\pi'$, where $\\pi'$ is defined recursively for $q = 1, 2, \\dots, m - 1$ by the equation\n",
    "\n",
    "> $\\displaystyle\n",
    "\\pi'[q] = \\left \\{\n",
    "\\begin{array}{ll}\n",
    "0 & \\text{if}~ \\pi[q] = 0, \\\\\n",
    "\\pi'[\\pi[q]] & \\text{if}~ \\pi[q] \\ne 0 ~\\text{and}~ P[\\pi[q] + 1] = P[q + 1] \\\\\n",
    "\\pi[q] & \\text{if}~ \\pi[q] \\ne 0 ~\\text{and}~ P[\\pi[q] + 1] \\ne P[q + 1] \\\\\n",
    "\\end{array}\n",
    "\\right .\n",
    "$\n",
    "\n",
    "> Explain why the modified algorithm is correct, and explain in what sense this change constitutes an improvement."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $P[q + 1] \\ne T[i]$, then if $P[\\pi[q] + q] = P[q + 1] \\ne T[i]$, there is no need to compare $P[\\pi[q] + q]$ with $T[i]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.4-7\n",
    "\n",
    "> Give a linear-time algorithm to determine whether a text $T$ is a cyclic rotation of another string $T'$. For example, $\\text{arc}$ and $\\text{car}$ are cyclic rotations of each other."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find $T'$ in $TT$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 32.4-8 $\\star$\n",
    "\n",
    "> Give an $O(m|\\Sigma|)$-time algorithm for computing the transition function $\\delta$ for the string-matching automaton corresponding to a given pattern $P$. (Hint: Prove that $\\delta(q, a) = \\delta(\\pi[q], a)$ if $q = m$ or $P[q + 1] \\ne a$.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compute the prefix function $m$ times."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}