C++로 구현하는 유한 오토마타 기반 문자열 검색 프로그램

유한 오토마타 기반 문자열 검색이란?

유한 개수의 상태를 가지는 오토마타를 유한 오토마타(Finite Automaton)라고 합니다. 여기서 소개하는 C++ 프로그램은 유한 오토마타를 이용해 문자열 검색을 수행합니다. 길이가 T인 텍스트 text[0 … T-1]과 길이가 P인 패턴 p[0 … P-1]이 주어졌을 때, 텍스트 안에서 패턴이 등장하는 모든 위치(인덱스)를 찾아 출력하는 것이 목표입니다.

이 방식은 검색에 앞서 패턴에 대한 전이 테이블(Transition Table)을 미리 구성해 둡니다. 덕분에 실제 검색 단계에서는 텍스트를 한 번만 순회하면 되므로 매우 효율적이며, 같은 패턴으로 여러 문서를 반복해서 검색할 때 특히 유리합니다.

알고리즘

전이 테이블을 생성하는 절차는 다음과 같습니다.

시작
    함수 void transitiontable():
    1) 첫 번째 행을 채웁니다. 첫 번째 행의 모든 항목은 p[0] 문자에 해당하는 칸을 제외하면 항상 0이며, p[0] 문자를 만나면 항상 상태 1로 이동합니다.
    2) 최장 접두사·접미사 길이(longestprefixsuffix)를 0으로 초기화합니다.
    3) i = 1부터 P까지 반복합니다. (여기서 P는 패턴의 길이)
        a) longestprefixsuffix와 같은 인덱스의 행에서 항목 값을 복사합니다.
        b) p[i] 문자에 대한 항목을 i+1로 갱신합니다.
        c) longestprefixsuffix = TT[lps][pat[i]]로 갱신합니다. (TT는 구성 중인 2차원 배열)
끝

C++ 구현 예제

#include<iostream>
#include<cstring>
#define NO_OF_CHARS 512
using namespace std;

// 주어진 패턴에 대한 유한 오토마타를 나타내는 TF 테이블을 생성한다
void transitiontable(char *p, int P, int TT[][NO_OF_CHARS]) {
    int i, longestprefixsuffix = 0, y;
    // 첫 번째 행 채우기
    for (y = 0; y < NO_OF_CHARS; y++)
        TT[0][y] = 0;
    TT[0][p[0]] = 1;
    // 나머지 행 채우기
    for (i = 1; i <= P; i++) {
        // longestprefixsuffix 행의 값 복사
        for (y = 0; y < NO_OF_CHARS; y++)
            TT[i][y] = TT[longestprefixsuffix][y];
        // 항목 갱신
        TT[i][p[i]] = i + 1;
        // 다음 행을 위해 lps 갱신
        if (i < P)
            longestprefixsuffix = TT[longestprefixsuffix][p[i]]; // TT는 구성 중인 2차원 배열
    }
}

// 텍스트에서 패턴이 나타나는 모든 위치를 출력한다
void patternsearch(char *p, char *t) {
    int P = strlen(p);
    int T = strlen(t);
    int TT[P+1][NO_OF_CHARS];
    transitiontable(p, P, TT);
    // 유한 오토마타 위에서 텍스트를 처리한다
    int i, j = 0;
    for (i = 0; i < T; i++) {
        j = TT[j][t[i]];
        if (j == P) {
            cout << "
 패턴이 발견된 인덱스: " << i-P+1;
        }
    }
}

int main() {
    char *text = "AABAA ABBAACCDD CCDDAABAA"; // 텍스트 입력
    char *pattern = "AABAA";                  // 패턴 입력
    patternsearch(pattern, text);
    getchar();
    return 0;
}

참고: 코드의 int TT[P+1][NO_OF_CHARS]는 가변 길이 배열(VLA)로, GCC나 Clang에서는 컴파일되지만 C++ 표준은 아닙니다. 표준을 엄격히 준수하려면 std::vector 기반의 2차원 배열을 사용하는 것이 좋습니다. 또한 NO_OF_CHARS를 512로 설정하여 확장 ASCII 영역의 문자까지도 처리할 수 있도록 했습니다.

실행 결과

패턴이 발견된 인덱스: 0
패턴이 발견된 인덱스: 20

동작 원리 정리

전이 테이블 TT는 현재 상태와 입력 문자를 받아 다음 상태를 알려주는 역할을 합니다. 검색은 상태 0에서 시작해 텍스트의 각 문자를 차례대로 입력하며 상태를 전이하는 방식으로 진행됩니다. 상태가 패턴의 길이 P에 도달하면 패턴이 완전히 일치한 것이므로, 해당 시점의 시작 인덱스(i - P + 1)를 출력합니다.

시간 복잡도를 살펴보면, 전처리(테이블 생성)에는 O(P × NO_OF_CHARS)가 필요하지만 실제 검색은 텍스트 길이에 비례하는 O(T)로 완료됩니다. 텍스트를 되돌아가지 않고 한 방향으로만 진행하기 때문에 스트리밍 환경에서도 활용할 수 있는 강력한 문자열 검색 기법입니다.