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;
}
}
'2023 1학기 > 자료구조' 카테고리의 다른 글
[자료구조/c언어] Using Dfs to print Equivalence Relation (0) | 2023.04.04 |
---|---|
[자료구조/c언어] Equivalence Relation (0) | 2023.04.04 |
[자료구조/c언어] 시간복잡도 (0) | 2023.04.02 |
[자료구조/c언어] 명제와 수학적 귀납법을 재귀함수를 통해서 이해 (0) | 2023.04.02 |
[자료구조/c언어]1. 메모리와 CPU (0) | 2023.04.02 |