아나그램 부분 문자열 검색이란?
이 문제에서는 길이가 n인 텍스트(text) 문자열과 길이가 m인 패턴(pattern) 문자열 두 개가 주어지며, 텍스트 안에서 패턴과 그 모든 순열(아나그램)이 나타나는 위치를 찾는 것이 목표입니다.
예를 들어 이해해 보겠습니다.
입력
text = "xyztrwqyzxfg"
pattern = "xyz"
출력
Found at index 0
Found at index 7
위 예시에서 인덱스 0의 "xyz"와 인덱스 7의 "yzx"는 서로 글자의 순서만 다른 아나그램 관계이므로, 두 위치 모두 결과로 출력됩니다.
문제 해결 접근 방법
이 문제는 라빈-카프(Rabin-Karp) 알고리즘과 유사한 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 패턴에 포함된 각 문자의 출현 빈도를 저장하는 배열을 만듭니다.
- 텍스트에서 패턴과 같은 길이만큼의 슬라이딩 윈도우를 설정하고, 윈도우 내 문자들의 빈도를 별도의 배열에 기록합니다.
- 윈도우를 한 칸씩 오른쪽으로 이동시키면서 매번 두 빈도 배열을 비교합니다.
- 두 배열이 완전히 일치하면 해당 위치에서 패턴의 아나그램이 존재한다는 의미이므로 시작 인덱스를 출력합니다.
이 방식은 각 윈도우를 이동할 때 새로 들어오는 문자의 빈도를 1 증가시키고, 밀려나는 문자의 빈도를 1 감소시키기만 하면 되므로 전체 시간 복잡도는 O(n) 수준으로 효율적입니다.
C++ 구현 코드
다음은 위 알고리즘을 구현한 전체 코드입니다.
#include <cstring>
#include <iostream>
#define MAX 256
using namespace std;
// 두 빈도 배열이 일치하는지 확인하는 함수
bool matchPattern(char arr1[], char arr2[]){
for (int i = 0; i < MAX; i++)
if (arr1[i] != arr2[i])
return false;
return true;
}
// 아나그램 패턴 검색 함수
void anagramSearch(char* pattern, char* text){
int M = strlen(pattern);
int N = strlen(text);
char patternArray[MAX] = { 0 }, textArray[MAX] = { 0 };
// 첫 번째 윈도우의 문자 빈도 계산
for (int i = 0; i < M; i++) {
(patternArray[pattern[i]])++;
(textArray[text[i]])++;
}
// 윈도우를 한 칸씩 이동하며 빈도 배열 비교
for (int i = M; i < N; i++) {
if (matchPattern(patternArray, textArray))
printf("\nPattern found at index value : %d", (i-M));
(textArray[text[i]])++;
textArray[text[i - M]]--;
}
// 마지막 윈도우 검사
if (matchPattern(patternArray, textArray))
printf("\nPattern found at index value: %d", (N-M));
}
int main() {
char text[] = "xyztrwqyzxfg";
char pattern[] = "xyz";
printf("Searching Anagram pattern in the string ");
anagramSearch(pattern, text);
return 0;
}
실행 결과
Searching Anagram pattern in the string
Pattern found at index value: 0
Pattern found at index value: 7
정리
이 프로그램은 크기 256의 정수형 빈도 배열 두 개를 활용하여, 텍스트 내에서 패턴과 그 아나그램이 등장하는 모든 위치를 선형 시간에 찾아냅니다. 단순히 문자열을 일일이 비교하는 브루트포스 방식(O(n×m×m))보다 훨씬 효율적이며, 슬라이딩 윈도우와 빈도 카운팅 기법을 함께 사용하는 대표적인 문자열 처리 알고리즘 사례입니다.