4. DFA 알고리즘

Reference : 
- 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님
- https://inuplace.tistory.com/314 / 이누의 개발성장기

DFA 알고리즘

• Naive 알고리즘에서 각 숫자에 대한 표기를 좀 더 하는 방식이다.
• 첫 글자와 일치하는 곳이 발견되면 그곳에 1을 표기하고, 그 이후로도 일치할 경우 1씩 더 증가시키면서 표기한다.
• 만약 표기하려는 수가 이미 표기된 수보다 작다면 표기할 수 없다.
• abcabcd에서 abcd를 찾는다면 abcabcd에는 1231234가 표기될 것이다.
• 찾으려는 글자의 길이 값이 표기된 갯수가 정답의 갯수가 될 것이다.
• 이에 대한 경우의 수를 표로 만들어 저장하고, 이를 활용한다.
• 다음은 abcabcd를 찾을 때 경우의 수 표이다. 위 숫자의 표기까지 진행됐을 때, 다음 문자가 a,b,c,d 중 무엇이냐에 따라 다음 표기가 달라짐을 나타낸다.

 

• 해당 테이블을 DFA 트랜지션 테이블이라고 한다.
• 어떤 패턴을 주면 이러한 테이블을 생성하는 알고리즘이 존재한다. (이는 O(ΣM)의 시간복잡도, 공간복잡도를 가진다.)
• ΣM : M을 사용하는 문자 종류만큼 더한 것(abcabcd를 찾는 경우 7*4), 트랜지션 테이블 공간 크기
• 시간복잡도 : O(ΣM + N), 트랜지션 테이블 제작시간 + for문
• 공간복잡도 : O(ΣM), 트랜지션 테이블 공간

---

DFA 알고리즘 예제

int Table[4][8] = { {1,1,1,4,1,1,4,1} ...}; // abcabcd 문자열을 찾을 때 트랜지션 테이블

int DFAmatch(char T[], int n, int output[]) {
    int i, s;
    i = 0; s = 0;
    
    output[i] = s; 
    // 0번째 글자는 0이라는 것을 의미, 테이블을 활용하기 위해선 해당 값이 필요하므로 우선 이렇게 시작
    
    for (i=1; i<=n; i++) { // 첫번째 글자부터 확인
        output[i] = Table[T[i] - 'a'][s]; 
        // 피대상 문자열의 i번째 값에서 'a'를 뺀다. 그러면 0~3 사이의 값이 나온다. 이를 활용한다.
        // s는 직전 문자를 나타내므로 테이블에서 적절한 값을 가져올 수 있게된다. 이를 output에 넣어준다.
        
        s = output[i]; // 다음에 돌때의 s값을 활용하기 위해 넣어준다.
    }
}