プログラマ専用SNS ミクプラ

#include <stdio.h>
#include <string.h>

#define NOMATCH -1

void makenext(unsigned char *p, int *next);
int  bm(char *p, char *t);

int main() {

  char text[/url]    = "ABCXDEZCABACABAC";
  char pattern[/url] = "ABAC";
  int result;

  result = bm(pattern, text);

  if(-1 == result) printf("NOMATCH\n");
  else             printf("MATCH, MATCHING POINT FROM %d\n", result + 1);

  return 0;
}
int bm(char *p, char *t) {

  int plen = strlen(p);
  int tlen = strlen(t);
  int next[256];

  int i = 0, j = 0;

  makenext(p, next);

  i = plen - 1;

  while(i < tlen) {

     j = plen - 1;
     while(t == p[j]) {

          printf("\nwhile: t[%d] = %c, p[%d] = %c\n", i, t, j, p[j]);
          printf("	plen - j = %d\n", plen - j);
          printf("	plen     = %d\n", plen);
          printf("	j        = %d\n", j);
          printf("	i        = %d\n", i);
          printf("	next  = %d\n", next);
          printf(" next[ t ]  = %d\n\n", next[ t ]);

         if(j == 0) return i;
         --i; --j;
     }

     if(next > plen - j) {

          printf("\nif: t[%d] = %c, p[%d] = %c\n", i, t, j, p[j]);
          printf("	plen - j = %d\n", plen - j);
          printf("	plen     = %d\n", plen);
          printf("	j        = %d\n", j);
          printf("	i        = %d\n", i);
          printf("	next  = %d\n", next);
          printf(" next[ t[i] ]  = %d\n\n", next[ t[i] ]);

          i += next[ t[i] ];
     }
     else {

          printf("\nelse : t[%d] = %c, p[%d] = %c\n", i, t[i], j, p[j]);
          printf("	plen - j = %d\n", plen - j);
          printf("	plen     = %d\n", plen);
          printf("	j        = %d\n", j);
          printf("	i        = %d\n", i);
          printf("	next[i]  = %d\n", next[i]);
          printf(" next[ t[i] ]  = %d\n\n", next[ t[i] ]);

          i += plen - j;
     }
  }

  return NOMATCH;
}
void makenext(unsigned char *p, int *next) {

  int n, k;

  n = strlen(p);

  for(k = 0; k < 256; k++) {

     next[k] = n;
  }

  for(k = 0; k < n - 1; k++) {

     next[ p[k] ] = n - k - 1;
  }

  return;
}