\def\title{KMP\_f}

@* Knuth--Morris--Pratt.  This is a straight-from-the-book implementation of
the Knuth--Morris--Pratt algorithm for finding a pattern |p| in a text.  In
this version, we allow the text to be searched to be given in a file (possibly
|stdin|).

@c
@<Header files to include@>@/
@<Global variables@>@/
@<Functions@>@/
@<The main program@>

@ We must include the standard I/O definitions.

@<Header files...@>=
#include <stdio.h>
#include <stdlib.h>

@ We will do some homemade buffering in order to speed things up: characters
in the text to be searched will be read into the |buffer| array before we
process them.  To do this we set up appropriate pointers and counters.  

We also have the purely {\it ad hoc\/} assumption that |p| occurs not more
than |max_num_occ| number of times in the text (it would be easy to change
this).

@d max_num_occ 100
@d buf_size BUFSIZ

@<Global variables@>=
int c; /* current character, or number of characters just read */
int no_chars=0; /* this is the number of chars that have been read */
int matching_no=0;
int ind[max_num_occ];
char buffer[buf_size]; /* we read the input into this array */
char *buf_end=buffer; /* the first unused position in |buffer| */
int file_given=0;

@ Now we come to the general layout of the |main| function. 

@<The main...@>=
main (argc,argv)
    int argc; /* the number of arguments on the \UNIX/ command line */
    char **argv; /* the arguments themselves, an array of strings */
{@+
  @<Variables local to |main|@>@;
  @<Scan the command-line options@>@;
  @<Try to open |file_name|; |exit| if fail@>;
  @<Find all occurrences of pattern |p| in text; print results@>@;
  @<Close file@>@;
  return 0; /* Normal exit */
}

@ The pattern to be searched for will be kept in string |p| (should not be
longer than |max_pattern_length|).

@d max_patern_length 256

@<Var...@>=
char p[buf_size];  

@ The algorithm is implemented through two functions.  Actually, we write our
own string length function just for fun (so we have three functions). 

@<Functions@>=
int my_strlen(char *s)
{@+
  int l=0;
  while (*s!='\0') s++,l++;
  return l;
}

@ The two main functions, as seen in class, are as follows.  There is one
thing to watch out for: we have to recall that vectors start with index~|0| in
\.{C}, whereas the pseudocode we saw in class assumes that the strings start
at index~|1|.  Another more serious thing is that we are using |buffer| to
read the text in chunks.  Let us first consider the |prefix_function|.

@<Functions@>+=
int *prefix_function(char *p, int *m)
{@+
  int *pi;
  int k, q;

  *m=my_strlen(p);
  pi=(int *)malloc((*m)*sizeof(int));
  *pi=0;
  k=0;
  for (q=1; q<*m; q++) {
    while ((k>0)&&(p[k]!=p[q]))
      k=pi[k-1];
    if (p[k]==p[q])
      k++;
    pi[q]=k;
  }
  return pi;
}


@ Here we rewrite the main routine of the Knuth--Morris--Pratt algorithm to
handle the fact that we have only part of the text in memory.  We still assume
that |t| points to the first character of the text to be searched.

@<Functions@>+=
void KMP(char *p)
{@+
  int m;
  int *pi;
  int i, q;
  char *t=buffer;

  pi=prefix_function(p, &m);
  q=0;
  @<Scan the text to look for |p|@>@;
}

@ Here is the crucial part of |KMP()|.

@<Scan the text to look for |p|@>=
while (1) {
  @<Fill |buffer| if it is empty; |break| at end of file@>;
  while ((q>0)&&(p[q]!=*t))
    q=pi[q-1];
  if (p[q]==*t)
    q++;
  if (q==m) {
    matching_no++;
    @<Record the fact that we had a matching@>@;
    q=pi[q-1];
  }
  t++,no_chars++;
}

@ We have to fill |buffer| when we have dealt with all of it.  

@<Fill |buffer| if it is empty; |break| at end of file@>=
if (t>=buf_end) {
  t=buffer; c=read(fd,t,buf_size);
  if (c<=0) break;
  buf_end=buffer+c;
}

@ Since in this implementation we assume that the user gave us a possibly
large file containing the text to be searched, we only print the number of
occurrences of the pattern in the text, and the places (``indices'' of the
first characters of the occurrences).  It would be easy to use this
information to print the lines in which the occurrences are (as |grep| does).

@<Record the fact that we had a matching@>=
ind[matching_no-1]=no_chars-m+1;

@ We read the pattern string |p| and the name of the file in which the text is
here.  In case the options \.{-f} is not given, we assume that the
user will provide us with the text in |stdin|.

@<Scan the command...@>=
*p=*file_name=*buffer='\0'; 
while (--argc) {
  if (sscanf(argv[argc],"-p%s", p)==1) ;
  else if (sscanf(argv[argc],"-f%s", file_name)==1) file_given=1;
  else {
    printf("Usage: %s [-p<pattern>][-f<file name>]\n", argv[0]);
    return -1;
  }
}

@ Here are some more local variables for |main|.

@d file_name_length 64

@<Global var...@>+=
char file_name[file_name_length];
int fd=0;  /* file descriptor, initialized to |stdin| */

@ @d READ_ONLY 0 /* read access code for system |open| routine */

@<Try to open...@>=
if ((file_given)&&(fd=open(file_name,READ_ONLY))<0) {
  printf("%s: cannot open file %s\n", argv[0], file_name);
  exit(-1);
} 

@ @<Close file@>=
close(fd);

@ The call to the functions to do the main job (finding |p| in text) is just
this. 

@<Find all occurrences of pattern |p| in text; print results@>=
KMP(p);
@<Print the indices of the first characters of |p| in the text@>@;

@ The output generated by this program is sort of boring.

@<Print the indices of the first characters of |p| in the text@>={@+
  int i;
  if (file_given)
    printf("Number of times \"%s\" occurs in file \"%s\" is %d.\n",
          p, file_name, matching_no);
  else printf("Number of times \"%s\" occurs in stdin is %d.\n",
          p, matching_no);
  printf("The occurrences start at characters with indices...: ");
  for (i=0; i<matching_no; i++)
    printf("%d ", ind[i]);
  printf("\n");
}

@* Index.
Here is a list of the identifiers used, and where they appear. Underlined
entries indicate the place of definition.