c implementation of knuth-morris-pratt algorithm for exact string matching.

kmp.c

#include <stdarg.h>
#include <stdio.h>
#include <string.h>
#define P_SIZE 7

int F[P_SIZE] ;

void prefix(char* p, int m) {
  
	int i = 1, j = 0;
	while(i < m) {
		if(p[i] == p[j]) {
			F[i] = j+1;
			i++;
			j++;
		}
		else if(j > 0) {
			j = F[j-1];
		}
		else {
			F[i] = 0;
			i++;
		}
	}
}
int main (int argc, char const *argv[])
{
	int i, j, position = -1;
	char T[] = "bacbabababacaca";
	char P[] = "ababaca";
	printf("T = %s\n", T);
	printf("P = %s\n", P);
	prefix(P, 7);
	printf("Prefix array = ");
	for(i = 0; i < 7; i++) {
		printf("%d ", F[i]);
	}
	
	i = j = 0;
	while(i < strlen(T)) {
		if(T[i] == P[j]) {
			if(j == 6) {
				position = i - j;
				break;
			}
			else {
				i++;
				j++;
			}
		}
		else if(j > 0) {
			j = F[j - 1];
		}
		else {
			i++;
		}
	}
	printf("\nposition of P in T is = %d\n", position);
	return 0;
}