이 글에서는 문자열 패턴 검색(Pattern Searching) 문제를 해결하기 위해 유한 오토마타(Finite Automata) 알고리즘을 활용하는 C++ 프로그램을 살펴보겠습니다.
문제 조건은 다음과 같습니다. 길이 n의 텍스트 text[0...n-1]과 길이 m의 패턴 pattern[0...m-1]이 주어졌을 때, 텍스트 안에서 패턴이 등장하는 모든 위치(인덱스)를 찾아내야 합니다.
유한 오토마타 패턴 검색의 동작 원리
유한 오토마타 기반 접근 방식은 크게 두 단계로 이루어집니다.
1. 전처리(Preprocessing) 단계: 패턴을 분석하여 2차원 배열 형태의 상태 전이 테이블(TF 테이블)을 만듭니다. 이 테이블은 '현재 상태에서 특정 문자를 입력받으면 어느 상태로 이동하는가'를 모두 기록합니다.
2. 검색(Searching) 단계: 텍스트의 문자를 처음부터 한 글자씩 읽어 가며 오토마타의 상태를 전이시킵니다. 상태가 m(패턴의 길이)에 도달하면 그 지점에서 패턴이 발견된 것입니다.
전처리 과정에서 오토마타를 한 번만 구축해 두면, 실제 검색은 텍스트를 되돌아가지 않고 선형으로 순회하기 때문에 매우 빠르게 동작한다는 것이 이 알고리즘의 핵심 장점입니다.
C++ 구현 코드
#include<stdio.h>
#include<string.h>
#define total_chars 256
int calc_nextstate(char *pat, int M, int state, int x) {
if (state < M && x == pat[state])
return state+1;
int ns, i;
for (ns = state; ns > 0; ns--) {
if (pat[ns-1] == x) {
for (i = 0; i < ns-1; i++)
if (pat[i] != pat[state-ns+1+i])
break;
if (i == ns-1)
return ns;
}
}
return 0;
}
// 유한 오토마타(전이 테이블)를 구축하는 함수
void calc_TF(char *pat, int M, int TF[][total_chars]) {
int state, x;
for (state = 0; state <= M; ++state)
for (x = 0; x < total_chars; ++x)
TF[state][x] = calc_nextstate(pat, M, state, x);
}
// 텍스트에서 패턴이 등장하는 모든 위치를 출력하는 함수
void calc_occur(char *pat, char *txt) {
int M = strlen(pat);
int N = strlen(txt);
int TF[M+1][total_chars];
calc_TF(pat, M, TF);
int i, state=0;
for (i = 0; i < N; i++){
state = TF[state][txt[i]];
if (state == M)
printf ("\n Given pattern is found at the index%d",i-M+1);
}
}
int main() {
char *txt = "AABCDAABBDCAABADAABDABAABA";
char *pat = "AABA";
calc_occur(pat, txt);
return 0;
}출력 결과
Given pattern is found at the index 11 Given pattern is found at the index 22
코드 설명
calc_nextstate() 함수는 현재 상태(state)와 입력 문자(x)가 주어졌을 때 다음 상태를 계산합니다. 입력 문자가 패턴의 다음 문자와 일치하면 상태를 1 증가시키고, 일치하지 않으면 가장 긴 접미사가 접두사와 일치하는 지점을 찾아 적절한 이전 상태로 되돌아갑니다.
calc_TF() 함수는 0부터 M까지의 모든 상태와 256개의 모든 가능한 문자 조합에 대해 다음 상태를 미리 계산하여 전이 테이블을 완성합니다.
calc_occur() 함수는 실제 검색을 수행합니다. 텍스트의 각 문자를 읽을 때마다 전이 테이블을 참조해 상태를 갱신하고, 상태가 M에 도달하면 패턴의 시작 인덱스(i-M+1)를 출력합니다.
시간 복잡도
전처리 단계의 시간 복잡도는 O(m × |Σ|)입니다. 여기서 |Σ|는 문자 집합(alphabet)의 크기로, 위 코드에서는 256입니다. 검색 단계는 텍스트를 한 번만 순회하므로 O(n)입니다. 따라서 전체 시간 복잡도는 O(m × |Σ| + n)이 됩니다.
검색 자체가 선형 시간에 처리되고 텍스트를 역방향으로 다시 확인할 필요가 없기 때문에, 동일한 패턴으로 여러 개의 긴 텍스트를 반복해서 검색해야 하는 상황에서 특히 효율적인 알고리즘입니다.