[자료구조/c언어] naive 알고리즘, DFA 알고리즘

naive 알고리즘, DFA 알고리즘

처음에는 어려웠다.

그렇지만 코드로 구현해보니, 괜찮았다.

<naive code>

#define max(a,b) ((a) < (b) ? (a) : (b))
#include <stdio.h>
#include <stdlib.h>
void naivematch(char T[], int n, char P[], int m, int* output)
{
	int i, j;
	for (i = 0; i < n; i++)
	{
		j = 0;
		while (j < m && P[j] == T[i + j]) {
			output[i + j] = max(output[i + j], j + 1); j++;
		}
	}
}
int main() {
	char T[] = { 'a','b','a','b','a','b','c','a','b','c','a','b','c','d','a','b','c','c','b','a','a','b','d','a','b','c','a','b','c','d','a','b','c','d'};
	char P[] = { 'a','b','c','a','b','c','d' };
	int n = sizeof(T) / sizeof(char);
	int m = sizeof(P) / sizeof(char);
	int output[100] = { 0 };
	//int* output = (int*)malloc(sizeof(int) * n);


	naivematch(T, n, P, m, output);
	int count = 0;
	for (int i = 0; i < n;i++)
	{
		if (output[i] == m) {
			count++;
			printf("The answer index ends at index %d\n", i);
		}
	}
	printf("Total count : %d", count);
	//free(output);

	return 0;
}
//for (int i = 1; i <= n - m + 1; i++)
//{
//	for (j = i; k = 1; k <= m; j++, k++)
//		if (T[j] != P[k])
//			break;
//	if (k == m + 1) output[j - 1] = 1;
//}

 

DFA는 위 상황에서 규칙 2차원배열이 주어진 상황이다.

<dfa code>

dfa는 핵심 코드만 쓰겠다.

int Table[4][8] = { {1,1,1,4,1,1,4,1}, ... };//dfa 알고리즘 테이블

int DFAmatch(char T[], int n, int output[])
{
	int i, s; //s:현재 상태
	s = 0;
	for (i = 0; i < n; i++) {
		s = Table[T[i] - 'a'][s];
		output[i] = s;
	}
}