kmp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <tchar.h>
#include <stdlib.h>
#include <string.h>
int nfind(int start, int lasts, int lastp, int endmatch, char *string, char *pat);
#define max_string_size 100
#define max_pattern_size 100
#define max_text_size 10000
int pmatch(int i, char *string, char *pat);
void fail(char *pat);
int failure[max_pattern_size];

int main()
{
	char text_array[max_text_size] = {0};
	char search[max_pattern_size] = {0};
	int kor = 0;
	char fname[30] = {0};
	printf("text를 담은 파일명을 입력하시오:");
	scanf("%s", fname);
	FILE *f;
	if ((f = fopen(fname, "r+")) == NULL)
	{
		if ((f = fopen(fname, "w+")) == NULL)
		{
			printf("파일이 열리지 않습니다\n");
			exit(1);
		}
	}
	fread(text_array, 10000, 1, f);
	puts(text_array);
	printf("탐색할 단어를 입력하세요:");
	scanf("%s", search);

	int start = 0;
	int lasts = strlen(text_array) - 1; //string 배열의 마지막 문자 인덱스
	int lastp = strlen(search) - 1;		//pat 배열의 마지막 문자 인덱스
	int endmatch = lastp;
	int i, num = 0;

	while (1)
	{
		if (nfind(start, lasts, lastp, endmatch, text_array, search) == -1)
			break;
		else
		{
			num = nfind(start, lasts, lastp, endmatch, text_array, search);
			printf("%d ", num);
			for (i = num; i < num + 40 + kor; i++)
			{
				if (text_array[i] & 0x80)
				{
					printf("%c%c", text_array[i], text_array[i + 1]);
					kor++;
					i++;
				}
				else if (!(text_array[i] & 0x80))
				{
					printf("%c", text_array[i]);
				}
			}
			kor = 0;
		}
		printf("\n");
		start = num + 1;
		endmatch = num + lastp + 1;
	}

	fclose(f);
	printf("\nKMP 방법\n");
	int cnt = 0;
	fail(search);
	while (1)
	{
		if (pmatch(cnt, text_array, search) == -1)
		{
			break;
		}
		else
		{
			num = pmatch(cnt, text_array, search);
			printf("%d ", num);
			for (i = num; i < num + 40 + kor; i++)
			{
				if (text_array[i] & 0x80)
				{
					printf("%c%c", text_array[i], text_array[i + 1]);
					kor++;
					i++;
				}
				else if (!(text_array[i] & 0x80))
				{
					printf("%c", text_array[i]);
				}
			}
			kor = 0;
			printf("\n");
			cnt = num + 1;
		}
	}
	return 0;
}

int nfind(int start, int lasts, int lastp, int endmatch, char *string, char *pat)
{ //비효율적인 방법
	int i, j;
	for (i = 0; endmatch <= lasts; endmatch++, start++) //endmatch가 lasts까지 올때까지
	{
		if (string[endmatch] == pat[lastp])
		{
			for (j = 0, i = start; j < lastp && string[i] == pat[j]; i++, j++) //j가 lastp보다 작고 string[i]와 pat[j]가 같으면 i++,j++
				if (j == lastp - 1)											   //마지막까지 검사, j가 lastp까지 오면 매칭 성공
					return start;
		}
	}
	return -1;
}

void fail(char *pat)
{ //가장 중요한 부분.
	int i, j;
	int n = strlen(pat);
	failure[0] = -1; //시작지점은 -1

	for (j = 1; j < n; j++)
	{
		// decide failure[j]; failure[j]번째 칸의 값을 구한다. (어디까지 최대로 같은가)
		i = failure[j - 1];						   //i에는 이전 칸의 인덱스값이 들어간다. 즉, 바로 앞은 i 까지 같았다.
		while ((i >= 0) && (pat[i + 1] != pat[j])) //i가 0 이상인데 이번칸의 정보가 i 다음칸과 다른 상태라면
			i = failure[i];						   //i에는 i번째에 든 인덱스값이 들어간다.(반복)
		if (pat[i + 1] == pat[j])				   //그러고는 바뀐 i의 다음 칸과 현재 칸의 정보가 같으면
			failure[j] = i + 1;					   //값을 1 늘인다.
		else
			failure[j] = -1; //다 해당되지 않으면 -1을 넣는다.
	}
}

int pmatch(int i, char *string, char *pat)
{ /* Knuth, Morris, Pratt string matching algorithm */
	int j = 0;
	int lens = strlen(string);
	int lenp = strlen(pat);
	while (i < lens && j < lenp)
	{
		if (string[i] == pat[j]) //일치하면 한칸씩 다음 문자 탐색
		{
			i++;
			j++;
		}
		else if (j == 0)
			i++; //일치하지 않고 탐색하는 부분이 아직 패턴의 시작점이라면 다음 문자로.
		else	 //일치하지는 않는데 탐색하는 부분이 패턴의 시작점이 아니라면
			j = failure[j - 1] + 1;
	}
	if (j == lenp)
		return (i - lenp); //일치하는 패턴을 찾았다면 문자열에서 패턴의 시작지점을 반환하자.
	else
		return -1; //못찾았다면 -1을 반환하자.
}

이상하게도 원래 되던 한글입력에 대해서는 작동을 안하지만, 해당 문제는 kmp에 대한 기능공부가 아니기때문에 넘어갔다.

나중에 여유로울때 다시 보도록 하자.