아나그램 패턴 검색 알고리즘 – 문자열에서 패턴의 모든 순열 찾기

아나그램(Anagram)은 주어진 문자열이나 패턴의 문자들을 재배열하여 만들 수 있는 모든 순열을 뜻합니다. 일반적인 패턴 검색 알고리즘이 텍스트에서 정확히 일치하는 패턴만 찾는 것과 달리, 아나그램 패턴 검색은 패턴 자체뿐 아니라 그 패턴으로 만들 수 있는 모든 가능한 배열까지 함께 찾아냅니다.

예를 들어 패턴이 "AABC"라면, 텍스트 안에서 "AABC", "AACB", "ABAC", "ABCA"처럼 문자의 종류와 개수가 동일한 부분 문자열을 모두 탐색하게 됩니다.

접근 방식

이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 해결할 수 있습니다.

전체 텍스트를 패턴 길이와 같은 크기의 윈도우(창) 단위로 나눕니다.
패턴의 각 문자별 출현 횟수를 계산하여 빈도 배열(patternFreq)에 저장합니다.
각 윈도우에 대해서도 문자별 빈도 배열(stringFreq)을 만듭니다.
두 배열이 완전히 일치하면 해당 위치에서 아나그램이 발견된 것입니다.

두 문자열이 아나그램 관계인지 판단하려면 문자의 종류와 개수가 정확히 같은지만 확인하면 되므로, 빈도 배열의 비교가 이 알고리즘의 핵심입니다.

시간 복잡도: 아나그램 패턴 검색 알고리즘의 시간 복잡도는 O(n)입니다. 매번 빈도 배열을 처음부터 다시 계산하는 대신, 윈도우가 한 칸 이동할 때 빠져나가는 문자는 감소시키고 새로 들어오는 문자만 증가시키는 방식으로 최적화하면 불필요한 반복 계산을 줄여 더욱 효율적으로 동작하게 할 수 있습니다.

입력 및 출력

입력:
메인 문자열 "AABAACBABBCABAABBA", 패턴 "AABC"

출력:
Anagram found at position: 2
Anagram found at position: 3
Anagram found at position: 4
Anagram found at position: 10

알고리즘

anagramSearch(text, pattern)

입력 − 메인 문자열과 패턴

출력 − 패턴과 그 아나그램들이 발견된 모든 위치

시작
    patternFreq 배열과 stringFreq 배열을 정의한다
    patLen := 패턴의 길이
    stringLen := 텍스트의 길이
    patternFreq 배열의 모든 값을 0으로 설정한다

    패턴에 포함된 모든 문자에 대해 반복
        해당 문자의 빈도를 증가시킨다
    반복 끝

    i := 0 부터 i <= stringLen - patLen 까지 반복
        stringFreq 배열의 모든 값을 0으로 설정한다
        현재 윈도우의 모든 문자에 대해 반복
            해당 문자의 빈도를 증가시킨다
        반복 끝

        만약 stringFreq와 patternFreq가 동일하다면
            i 값을 출력한다 (해당 위치에서 아나그램 발견)
    반복 끝
종료

C++ 구현 예제

#include<iostream>
#include<cstring>
#define LETTER 26
using namespace std;

// 두 배열이 동일한지 비교하는 함수
bool arrayCompare(int *array1, int *array2, int n) {
    for(int i = 0; i<n; i++) {
        if(array1[i] != array2[i])
            return false; // 하나라도 다르면 즉시 종료
    }
    return true; // 두 배열이 완전히 동일함
}

// 배열의 모든 요소를 지정한 값으로 초기화하는 함수
void setArray(int *array, int n, int value) {
    for(int i = 0; i<n; i++)
        array[i] = value;
}

void anagramSearch(string mainString, string patt, int *array, int *index) {
    int strFreq[LETTER], pattFreq[LETTER];
    int patLen = patt.size();
    int stringLen = mainString.size();
    setArray(pattFreq, LETTER, 0);       // 모든 빈도를 0으로 초기화

    for(int i = 0; i<patLen; i++) {
        int patIndex = patt[i] - 'A';    // 'A'의 ASCII 값 차감
        pattFreq[patIndex]++;            // 빈도 증가
    }

    for(int i = 0; i<=(stringLen - patLen); i++) {  // 윈도우가 이동하는 범위
        setArray(strFreq, LETTER, 0);               // 메인 문자열용 빈도 배열 초기화
        for(int j = i; j<(i+patLen); j++){          // 각 윈도우의 빈도 갱신
            int strIndex = mainString[j] - 'A';
            strFreq[strIndex]++;                    // 빈도 증가
        }

        if(arrayCompare(strFreq, pattFreq, LETTER)) {  // 두 배열이 동일한 경우
            (*index)++;
            array[*index] = i;                         // i번째 위치에서 아나그램 발견
        }
    }
}

int main() {
    string mainStrng = "AABAACBABBCABAABBA";
    string pattern = "AABC";
    int matchLocation[mainStrng.size()];
    int index = -1;
    anagramSearch(mainStrng, pattern, matchLocation, &index);

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

실행 결과

Anagram found at position: 2
Anagram found at position: 3
Anagram found at position: 4
Anagram found at position: 10

결과 해석

인덱스 2의 "BAAC", 인덱스 3의 "AACB", 인덱스 4의 "ACBA", 그리고 인덱스 10의 "CABA"는 모두 문자 A 2개, B 1개, C 1개로 구성되어 있습니다. 따라서 이 네 부분 문자열은 패턴 "AABC"의 아나그램에 해당하며, 알고리즘이 네 위치를 모두 정확히 찾아낸 것을 확인할 수 있습니다.