C 언어 데이터 구조 코드 - 직렬 KMP 일치 알고리즘 구현

Head.H

#define MAXSIZE 30

typedef struct _str
{
	char data[MAXSIZE];
	int len;
}Str, *str;

str InitString(void);
void PrintStr(str s);
void StrAssign(str s, char *ch);
void GetNextArray(str T, int *next);
int FindStringIndex_KMP(str s, str t);
int FindStringIndex(str s, str t);

 
 
Function.C

str InitString(void)
{
	str s = (str)malloc(sizeof(Str));
	return s;
}


void PrintStr(str s)
{
	if (s->len == 0)
	{
		printf("This String is empty ! 
");
		return;
	}

	for (int i = 0; i < s->len; i++)
	{
		printf("%c", s->data[i]);
	}
	printf("
");
}


void StrAssign(str s, char *ch)
{
	int i;
	for (i = 0; ch[i] != '\0'; i++)
	{
		if (i < MAXSIZE - 1)
		{
			s->data[i] = ch[i];
		}
	}
	s->len = i;
}


void GetNextArray(str S, int *next)
{
	next[0] = 0;
	int k = 0;    //     

	for (int i = 1; i < S->len; i++)
	{
		while (k > 0 && S->data[k] != S->data[i])
		{
			k = next[k - 1];
		}
		if (S->data[k] == S->data[i])//  p[0...k-1] k     
		{
			k = k + 1;
		}
		next[i] = k;
	}
}


int FindStringIndex_KMP(str s, str t)
{
	if (t->len > s->len)
	{
		printf("The string be found should shorter ! 
");
		return -1;
	}

	int *nextarray = (int*)malloc(sizeof(int)*t->len);
	GetNextArray(t, nextarray);

	int i = 0;
	int matchlen = 0;
	while ((i < s->len) && (s->len - i >= t->len))
	{
		if (s->data[i] == t->data[0]) //      
		{
			for (int j = 0; j < t->len; j++)
			{
				if (s->data[i + j] != t->data[j])
				{
					i = i + (matchlen - nextarray[matchlen - 1]);   //  next       ￥￥￥￥￥
					matchlen = 0;
					break;
				}
				else
				{
					matchlen++;
				}

				if (matchlen == t->len)
				{
					return i;
				}
			}
		}
		else  //   
		{
			i++;
		}
	}

	return -1;
}


int FindStringIndex(str s, str t)
{
	if (t->len > s->len)
	{
		printf("The string be found should shorter ! 
");
		return -1;
	}

	int i = 0;
	int matchlen = 0;
	while ((i < s->len) && (s->len - i >= t->len))
	{
		if (s->data[i] == t->data[0])
		{
			for (int j = 0; j < t->len; j++)
			{
				if (s->data[i + j] != t->data[j])
				{
					i++;
					matchlen = 0;
					break;
				}
				else
				{
					matchlen++;
				}

				if (matchlen == t->len)
				{
					return i;
				}
			}
		}
		else
		{
			i++;
		}
	}

	return -1;
}

 
 
Main.C

void main(void)
{
	char a[] = "BBC ABCDAB ABCDABCDABDE";
	char b[] = "ABCDABD";

	str S1 = InitString();
	str S2 = InitString();
	StrAssign(S1, a);
	StrAssign(S2, b);
	PrintStr(S1);       //BBC ABCDAB ABCDABCDABDE
	PrintStr(S2);       //ABCDABD


	int *next = (int*)malloc(sizeof(int)*S2->len);
	GetNextArray(S2, next);
	for (int i = 0; i < S2->len; i++)
	{
		printf("%d ", next[i]);
	}
	printf("
");


	int index = FindStringIndex_KMP(S1, S2);
	printf("Find index: %d 
", index);


	printf("
");
	system("pause");
}