아나그램(Anagram)은 동일한 문자들을 다른 순서로 재배치하여 만든 문자열을 의미합니다. 예를 들어 "listen"과 "silent"처럼 구성 문자는 같지만 순서만 다른 경우를 말합니다. 아나그램 부분 문자열 검색은 주어진 텍스트 안에서 특정 패턴의 아나그램에 해당하는 부분 문자열이 어느 위치에 있는지 찾아내는 알고리즘입니다.
다음은 자바(Java)로 구현한 아나그램 부분 문자열 검색 예제입니다.
예제 코드
public class Demo{
static final int max_val = 256;
static boolean compare_vals(char my_arr_1[], char my_arr_2[]){
for (int i = 0; i < max_val; i++)
if (my_arr_1[i] != my_arr_2[i])
return false;
return true;
}
static void search_subs(String my_pattern, String my_text){
int pat_len = my_pattern.length();
int txt_len = my_text.length();
char[] count_pat = new char[max_val];
char[] count_txt = new char[max_val];
for (int i = 0; i < pat_len; i++){
(count_pat[my_pattern.charAt(i)])++;
(count_txt[my_text.charAt(i)])++;
}
for (int i = pat_len; i < txt_len; i++){
if (compare_vals(count_pat, count_txt))
System.out.println("The element was found at index " + (i - pat_len));
(count_txt[my_text.charAt(i)])++;
count_txt[my_text.charAt(i-pat_len)]--;
}
if (compare_vals(count_pat, count_txt))
System.out.println("The element was found at index " + (txt_len - pat_len));
}
public static void main(String args[]){
String my_text = "ABNFGHABNJGH";
String my_pattern = "NFGH";
search_subs(my_pattern, my_text);
}
}
실행 결과
The element was found at index 2
위 출력 결과는 텍스트 "ABNFGHABNJGH"에서 패턴 "NFGH"의 아나그램이 인덱스 2 위치에서 발견되었음을 보여줍니다. 실제로 텍스트의 2번째 인덱스부터 시작하는 부분 문자열이 바로 "NFGH" 그 자체이므로 아나그램 조건을 만족합니다.
코드 동작 원리
1. Demo 클래스와 compare_vals 메서드
Demo 클래스에는 먼저 상수 max_val이 정의되어 있습니다. 이 값은 256으로 설정되어 있는데, 이는 확장 ASCII 코드로 표현할 수 있는 전체 문자 수를 나타내며 각 문자의 출현 빈도를 저장할 배열의 크기로 사용됩니다.
compare_vals 메서드는 두 개의 char 배열을 매개변수로 받는 불리언(Boolean) 함수입니다. 이 메서드는 두 배열을 처음부터 max_val까지 순회하며 각 인덱스의 값을 하나씩 비교합니다. 모든 요소가 동일하면 true를 반환하고, 하나라도 다른 값이 존재하면 false를 반환합니다. 즉, 두 문자 빈도 분포가 완전히 일치하는지 판단하는 역할을 합니다.
2. search_subs 메서드 — 슬라이딩 윈도우 기법
search_subs 메서드는 검색 대상 텍스트와 찾고자 하는 패턴을 인자로 받습니다. 먼저 두 문자열의 길이를 구한 뒤, 패턴용 빈도 배열(count_pat)과 텍스트용 빈도 배열(count_txt)을 크기 256으로 생성합니다.
첫 번째 반복문에서는 패턴의 각 문자와 텍스트 앞부분(pat_len 길이만큼)의 문자를 순회하면서 해당 문자의 등장 횟수를 각 배열에 누적합니다. 이렇게 하면 초기 윈도우와 패턴의 빈도 정보가 준비됩니다.
이후 두 번째 반복문이 실행되며 슬라이딩 윈도우(sliding window) 방식으로 탐색이 진행됩니다. 매 단계마다 현재 윈도우의 빈도 배열과 패턴의 빈도 배열을 compare_vals로 비교하고, 두 배열이 일치하면 해당 시작 위치(i - pat_len)의 인덱스를 출력합니다.
비교가 끝나면 윈도우를 한 칸 오른쪽으로 이동시키는데, 이때 새로 유입되는 문자의 카운트는 증가시키고 윈도우에서 벗어나는 문자의 카운트는 감소시킵니다. 덕분에 매번 배열을 처음부터 다시 셀 필요 없이 상수 시간(O(1)) 연산만으로 빈도 정보를 갱신할 수 있습니다.
반복문이 종료된 후에는 마지막 윈도우에 대한 비교를 한 번 더 수행하여, 텍스트의 끝부분에서 아나그램이 발견되는 경우도 놓치지 않도록 처리합니다.
3. main 메서드
main 메서드에서는 텍스트 "ABNFGHABNJGH"와 패턴 "NFGH"를 정의한 뒤 search_subs 메서드를 호출하여 검색 결과를 화면에 출력합니다.
시간 및 공간 복잡도
텍스트의 길이를 n이라 할 때, 각 윈도우 비교 시 최대 256번의 비교가 수행되므로 시간 복잡도는 O(n × 256), 즉 사실상 O(n)에 가깝습니다. 또한 고정 크기의 두 배열만 사용하므로 공간 복잡도는 O(1)입니다. 이는 가능한 모든 부분 문자열을 일일이 정렬하여 비교하는 브루트 포스(brute-force) 방식보다 훨씬 효율적인 접근법입니다.