%-*- Mode: latex-mathematica; fill-column: 75 -*-
%---TeX-start-of-header---
\documentclass[titlepage]{article}
\usepackage{mathematica,figi,alltt}
\mmanobreak

\newenvironment{implementation}%
  {\vspace{-0.4cm}\footnotesize\textbf{Implementation notes: }}{\bigskip}

\begin{comment}
\begin{mathematica}
<<tek.m;
\end{mathematica}

\begin{mathematica}
SetOptions["stdout", PageWidth->Infinity];
zero = 0.00001;
ohide = DisplayFunction->Identity;
oshow = DisplayFunction -> $DisplayFunction;
ojoin = PlotJoined -> True;
oall = PlotRange->All;
osurf = HiddenSurface->False;
deg = N[Degree];
pi = N[Pi];
\end{mathematica}

\end{comment}

\begin{document}
\psfiginit
%---TeX-end-of-header---

\author{Tomasz J.\ Cholewo}
\title{Design and Analysis of Computer Algorithms, EMCS\,619\\
Homework \#5}
\maketitle
%====================================================================
\section{Problem 1}
Verification of manual calculations.  The \texttt{fail} array:
\begin{mathematica}
KMPsetup["aabaabb"]
.
Out[9]= {0, 1, 2, 1, 2, 3, 4}
\end{mathematica}
Results of scan:
\begin{mathematica}
KMPmatch["abaabbabbaabaabaabb", "aabaabb"]
.
Out[11]= {13}
\end{mathematica}
%============================================================
\section{Problem 2}
Jump arrays:
\begin{mathematica}
Print @ computejumps["abcbabc"];
Print @ computematchjumps["abcbabc"];
.
{2, 1, 0, 7, 7}
{10, 9, 8, 7, 9, 8, 1}
\end{mathematica}
Test match:
\begin{mathematica}
BMmatch["abababcabadcbabcaebacedabbabcbabc", "abcbabc"]
.
Out[49]= {27}
\end{mathematica}

%====================================================================
\newpage
\section{Problem 3}

Pidgin-Pascal formulation of the algorithm.  It is a simple extension of te
straightforward matching algorithm.  Failure is signalled by return value 0.
\begin{alltt}
function SFwildmatch(t: String, p: String): Integer;
begin
  while (j <= m) and (i <= n) do begin
    if p(j) = '*' then
      if SFwildmatch(t + i, p + j + 1) <> 0 then   /* C-like pointer operations */
        return i - j + 1
      else
        return 0;
    else
      if t(i) = p(j) then
        i = i + 1; j = j + 1
      else
        i = i - j + 2; j = 1;
  end;
  if j > m then
    return i - m
  else
    return 0;
end;
\end{alltt}

Function \texttt{SFwildmatch} finds the position of the first match
between text \texttt{t}and pattern \texttt{p} which can contain any number
of `*' characters which work as wildcards.  For an empty pattern and
pattern beginning with `*' the function returns 1, for no match 0.
\begin{mathematica}
SFwildmatch[t_String, p_String] :=
Module[{i = 1, j = 1, n = StringLength[t], m = StringLength[p]},
  While[ j <= m && i <= n,
    If[ StringTake[p, {j}] == "*",
      If[ SFwildmatch[ StringTake[t, {i, n}], StringTake[p, {j + 1, m}] ] != 0,
        Return[i - j + 1],
        Return[0]
      ],
      If[ StringTake[t, {i}] == StringTake[p, {j}],
        i++; j++,
        i = i - j + 2; j = 1
      ]
    ]
  ];
  If[ j > m, i - m, 0 ]
]
\end{mathematica}
Some tests (four different patterns and the same text):
\begin{mathematica}
SFwildmatch["abcdef", #]& /@ {"a*c*f", "*ef", "c*e", "c*b"}
.
Out[33]= {1, 1, 3, 0}
\end{mathematica}
Textbook test case:
\begin{mathematica}
SFwildmatch["happysundaemonday", "sun*day"]
.
Out[34]= 6
\end{mathematica}
Normal straightforward scan algorithm has complexity $\Theta(mn)$.  For
this algorithm it remains the same because there is only one tail-recursive
call for each `*' in the pattern.  This recursion is equivalent to
iteration but this version is more readable.
%====================================================================
\end{document}