[java] 자바로 문자열 매칭 알고리즘 구현하기

15 Dec 2023

java

문자열 매칭 알고리즘은 특정 패턴이 주어진 문자열에 포함되어 있는지를 찾는 알고리즘입니다. 여기서는 가장 간단하고 대표적인 브루트 포스(brute force) 방식을 사용하여 이 알고리즘을 자바로 구현하는 방법을 살펴보겠습니다.

브루트 포스 문자열 매칭 알고리즘

브루트 포스 문자열 매칭 알고리즘은 주어진 패턴을 텍스트 문자열과 한 글자씩 비교하면서 일치 여부를 확인하는 방식입니다.

다음은 간단한 브루트 포스 문자열 매칭 알고리즘의 구현 예제입니다.

public class BruteForceStringMatch {
    public static int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }
            if (j == m) {
                return i; // 패턴이 일치하는 위치 반환
            }
        }
        return -1; // 일치하는 패턴이 없을 경우 -1 반환
    }

    public static void main(String[] args) {
        String text = "ABCABCDABABCDABCDABDE";
        String pattern = "ABCDABD";
        int index = search(text, pattern);
        if (index != -1) {
            System.out.println("패턴이 텍스트에서 발견됨. 위치: " + index);
        } else {
            System.out.println("패턴이 텍스트에서 발견되지 않음.");
        }
    }
}

위 코드에서 search 메서드는 주어진 텍스트 문자열에서 패턴을 찾아 해당 위치를 반환합니다. main 메서드에서는 주어진 예제를 실행하여 패턴을 찾는 과정을 보여줍니다.

마치며

이것은 브루트 포스 문자열 매칭 알고리즘의 간단한 구현 예제입니다. 브루트 포스는 간단하지만 효율성이 떨어지는 알고리즘이며, 더 효율적인 보이어-무어 문자열 매칭 알고리즘과 같은 다른 알고리즘들도 존재합니다. 따라서 실제 프로젝트에서는 해당 상황에 맞는 적절한 알고리즘을 선택하여 사용하는 것이 중요합니다.

이러한 문자열 매칭 알고리즘들은 자바뿐만 아니라 다른 프로그래밍 언어에서도 유용하게 활용될 수 있습니다.

참고문헌: GeeksforGeeks - Brute Force String Matching