[18-알고리즘] 문자열 탐색(String Match) 유한 상태 기계를 통한 문자열 탐색(String matching with finite automata)

유한 상태 기계는 다음과 같이 정의되어있습니다. 어떠한 사건(Event)에 의해 한 상태에서 다른 상태로 변화할 수 있으며, 이를 전이(Transition)이라 한다. (출처 : Wikipedia)

String matching with finite automata는 유한 상태 기계를 사용하여서 문자열을 탐색하는 것입니다.

[그림1] 택스트에 패턴이 있는지 확인하기 위해서 유한 상태 기계[그림2] 같이 만듭니다. 

그리고 Text에서 글자 하나가 유한 상태 기계의 하나의 입력값이 됩니다. 입력 값 하나가 들어오면 그게 맞는 상태로 변이가 일어납니다. 

[그림 2] 패턴을 가지고 유한 상태 기계를 만든 것입니다. 

출처 : https://www.ics.uci.edu/~eppstein/161/960222.html

[그림 3] 패턴 nano를 유한 상태 기계로 표시한 것입니다. 

이렇게 하나의 입력을 기준으로 다음 상태로 이동하는 것입니다. 

유한상태기계를 이용해서 문자열 탐색을 하면 편리한 점이 있습니다. 그러나 이렇게 유한 상태 기계로 만드는 과정은 복잡하고 오래 걸리는 므로 자주 활용되지는 않습니다.