Morris-Pratt Pattern Matching

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

#define OUTPUT(x)    printf("%d\n", x )

void preMp(char* x, int m, int mpNext[]) {
	int i, j;

	i = 0;
	j = mpNext[0] = -1;
	while (i < m) {
		while (j > -1 && x[i] != x[j])
			j = mpNext[j];
		mpNext[++i] = ++j;
	}
}

void MP(char* x, int m, char* y, int n) {
	int i, j, mpNext[256];

	/* Preprocessing */
	preMp(x, m, mpNext);

	/* Searching */
	i = j = 0;
	while (j < n) {
		while (i > -1 && x[i] != y[j])
			i = mpNext[i];
		i++;
		j++;
		if (i >= m) {
			OUTPUT(j - i);
			i = mpNext[i];
		}
	}
}

int main()
{
	freopen("output.txt", "w", stdout);
	//int mpNext[256];
	int i;
	char y[] = "how are you gagggagg world hello";
	char x[] = "gagggagg";

	/*
	preMp( x, strlen(x), mpNext );
	for(i=0; i<(strlen(x)+1); i++ )
		printf("%4d", mpNext[i] );
	printf("\n");
	*/
	MP(x, strlen(x), y, strlen(y));
	return 0;
}

x :            g a g g g a g g

mp Next : -1 0 0 1 1 1 2 3 4

 

x 랑 본문이 있었다 하면,

접두 접미사의 일치 수를 의미하는 것임

mpNext : 틀린 문자가 발견된 위치의 앞서 일치된 문자열속의 접두사와 접미사의 일치 수를 기록한 배열.

이것을 중간에 밀 수 있는 수를 찾을 수 있음 그래서 n을 전부 안돌아도 됨.

실제로 x 가 밀린다는 것은 i, j 가 가리키고 있는 부분의 문자열이 같을 때, i = mpNext[i]; 이렇게 됨.

미는 것과 인덱스를 앞으로 보내는 것을 동치로 봄.