정리 노트

이번 글에서는 DFA(Determistic Finite State of Automaton)을 이용해 문자열 안에서 특정 패턴을 찾는 방법에 대해 적어보겠습니다. Naive 한 방법 DFA로 들어가기 전에 왜 DFA를 써야 하는지 느끼기 위해 naive 하게 찾는 방법부터 보겠습니다. 예를 들어 문자열 "BLUERED"이 있고, 여기서 패턴 "RED"을 찾는 문제를 푼다고 합시다. RED를 찾는 가장 naive 한 방법은 하나하나 다 살펴보는 것입니다. 이렇게 하나하나 체크해서 패턴을 찾을 수 있습니다. 하지만 이렇게 찾는다면 시간이 오래 걸립니다. 문자열의 길이를 N, 패턴의 길이를 M이라고 한다면, time complexity는 O(NM)이라 표현할 수 있습니다. 그리고 이러한 방법은 매번 불일치가 일..