유한 오토마타(Finite Automata)를 활용한 효율적인 문자열 패턴 검색

유한 오토마타(Finite Automata, FA)를 구성하면 텍스트 안에서 특정 패턴을 매우 효율적으로 찾아낼 수 있습니다. 먼저 2차원 배열을 채워 오토마타의 전이 테이블(transition table)을 만들어야 하며, 일단 테이블이 완성되면 실제 검색 과정은 매우 단순해집니다. 오토마톤의 첫 번째 상태에서 출발하여 입력 문자를 하나씩 처리하다가 최종 상태(final state)에 도달하면, 그 지점에서 패턴이 문자열 내에 존재한다는 것을 의미합니다.

유한 오토마타를 구성하는 데 드는 시간 복잡도는 O(M×K)입니다. 여기서 M은 패턴의 길이, K는 서로 다른 문자의 개수입니다. 반면, 실제 패턴 검색 단계의 시간 복잡도는 O(n)으로, n은 텍스트의 길이입니다. 즉, 전처리 비용은 들지만 검색 자체는 선형 시간에 완료되므로 긴 텍스트에서 동일한 패턴을 반복해서 찾아야 하는 상황에 특히 유리합니다.

입력 및 출력

입력:
메인 문자열: "ABAAABCDBBABCDDEBCABC", 패턴 "ABC"
출력:
패턴 발견 위치: 4
패턴 발견 위치: 10
패턴 발견 위치: 18

알고리즘

fillTransTable(pattern, transTable)

입력 − 패턴과 전이 정보를 채워 넣을 전이 테이블

출력 − 전이 정보가 채워진 전이 테이블

Begin
    longPS := 0
    전이 테이블의 모든 항목을 0으로 초기화
    transTable[0, pattern[0]] = 1      // 패턴의 첫 번째 문자에 대한 처리

    for 패턴에 포함된 모든 문자 인덱스 i, do
        for 가능한 모든 문자 j, do
            transTable[i,j] := transTable[longPS, j]
        done

        transTable[i, pattern[i]] := i+1
        if i < 패턴 크기, then
            longPS := transTable[longPS, pattern[i]]
    done
End

이 함수의 핵심 아이디어는 접두사(prefix)와 접미사(suffix) 정보를 활용하여 각 상태에서의 전이를 결정하는 것입니다. longPS 변수는 현재까지 처리된 부분에서 가장 긴 접두사-접미사 일치 길이를 추적하며, 이를 통해 불일치가 발생했을 때 되돌아갈 상태를 효율적으로 계산할 수 있습니다.

patternSearch(text, pattern)

입력 − 메인 텍스트와 패턴

출력 − 패턴이 발견된 인덱스 목록

Begin
    patLen := 패턴 길이
    strLen := 문자열 길이
    fillTransTable(pattern, transTable) 호출
    present := 0

    for 텍스트의 모든 문자 인덱스 i, do
        present := transTable[present, text[i]]
        if present = patLen, then
            (i – patLen + 1) 위치에 패턴이 존재함을 출력
    done
End

C++ 구현 예제

#include<iostream>
#define MAXCHAR 256
using namespace std;

void fillTransitionTable(string pattern, int transTable[][MAXCHAR]) {
    int longPS = 0;

    for (int i = 0; i < MAXCHAR; i++) {
        transTable[0][i] = 0;         // 첫 번째 상태의 항목 생성
    }

    transTable[0][pattern[0]] = 1;    // 첫 문자에 대해 첫 상태로 이동
    for (int i = 1; i<= pattern.size(); i++) {

        for (int j = 0; j < MAXCHAR ; j++)   // 접두사/접미사를 이용해 상태 갱신
            transTable[i][j] = transTable[longPS][j];
        transTable[i][pattern[i]] = i + 1;
        if (i < pattern.size())
            longPS = transTable[longPS][pattern[i]]; // 다음 상태를 위한 최장 접두사-접미사 갱신
    }
}

void FAPatternSearch(string mainString, string pattern, int array[], int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();
    int transTable[patLen+1][MAXCHAR];    // 패턴별 전이 테이블 생성

    fillTransitionTable(pattern, transTable);
    int presentState = 0;

    for(int i = 0; i<=strLen; i++) {
        presentState = transTable[presentState][mainString[i]];   // 전이가 가능하면 다음 상태로 이동
        if(presentState == patLen) {     // 현재 상태가 최종 상태이면 패턴 발견
            (*index)++;
            array[(*index)] = i - patLen + 1 ;
        }
    }
}

int main() {
    string mainString = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    int locArray[mainString.size()];
    int index = -1;
    FAPatternSearch(mainString, pattern, locArray, &index);

    for(int i = 0; i <= index; i++) {
        cout << "Pattern found at position: " << locArray[i]<<endl;
    }
}

실행 결과

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

위 실행 결과에서 확인할 수 있듯이, 패턴 "ABC"는 메인 문자열의 4번째, 10번째, 18번째 위치에서 발견됩니다. 이 알고리즘은 KMP(Knuth-Morris-Pratt) 알고리즘과 같은 계열에 속하며, 전이 테이블만 미리 준비되어 있다면 텍스트를 한 번만 순회하면서 모든 패턴 발생 위치를 찾을 수 있다는 강력한 장점이 있습니다.