#include <stdio.h>
#include <string.h>
#define OUTPUT(x) printf("%d\n", x )
#define ASIZE 256
#define XSIZE 256
void preKmp(char* x, int m, int kmpNext[]) {
int i, j;
i = 0;
j = kmpNext[0] = -1;
while (i < m) {
while (j > -1 && x[i] != x[j])
j = kmpNext[j];
i++;
j++;
if (x[i] == x[j])
kmpNext[i] = kmpNext[j];
else
kmpNext[i] = j;
}
}
void KMP(char* x, int m, char* y, int n) {
int i, j, kmpNext[XSIZE];
/* Preprocessing */
preKmp(x, m, kmpNext);
/* Searching */
i = j = 0;
while (j < n) {
while (i > -1 && x[i] != y[j])
i = kmpNext[i];
i++;
j++;
if (i >= m) {
OUTPUT(j - i);
i = kmpNext[i];
}
}
}
int main()
{
freopen("output.txt", "w", stdout);
int i;
char y[] = "how are you gagggagg world hello";
char x[] = "gagggagg";
KMP(x, strlen(x), y, strlen(y));
return 0;
}
mpNext 에서 사실 if(x[i] == x[j]) kmpNext[i] = kmpNext[j]; 만 추가되었는데, 이게 얼마만큼의 성능이 좋아졌는지?
미리 비교 신공, 빵꾸 뚫기 신공!!!
미리 비교 해서 밀려야 한다면 미리 표에 반영했다는 것임
shift = i - kmpNext[i];
mpNext : -1 0 0 1 1 1 2 3 4
kmpNext: -1 0 -1 1 1 0 -1 1 4
'Computer Science' 카테고리의 다른 글
Generic swap (0) | 2021.04.24 |
---|---|
Boyer-Moore Pattern Matching (0) | 2021.04.24 |
Morris-Pratt Pattern Matching (0) | 2021.04.24 |
Shift Or pattern mathcing (0) | 2021.04.24 |
CRC 개념 (0) | 2021.04.24 |
댓글