[Algorithms] String Matching with Finite Automata | 오토마타를 이용한 문자열 매칭

String Matching with Finite Automata

오토마타를 이용한 문자열 매칭

* Finite Automata (유한 오토마타) (URL)
* String Matching Algorithms (문자열 매칭 알고리즘) (URL)

- 입력 문자열 \(\texttt{string}\)에서 부분문자열 \(\texttt{pattern}\)을 찾아내는데 Finite Automata(이하 FA)를 이용하는 방법이다.
- FA는 \(\texttt{string.size() + 1}\)개의 States로 구성되며,
  \(\texttt{string}\)을 입력받으며, \(\texttt{pattern}\)이 인식되면 Final State로 들어선다.

Example. \(\texttt{string}\) 내에서 문자열 "\(ababc\)"(\(=\texttt{pattern}\))를 찾아내는
FA의 Transition Graph와 Transition Function(\(\delta\))이 정의된 Table

---

Implementation (Pseudo Code)

findFA(str[], delta[][], finalState)
{ // str[1...n]에서 pattern[1...m]이 존재하는지를 판단한다.
    q ← 0;
    for i ← 1 to n
    {
        q ← delta(q, str[i]);
        if (q ∈ finalState)
        then str[i - m + 1] 에서 매칭이 발생되었음을 알린다.
}

---

Reference: 쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)