[java] 자바를 활용한 라빈 카프 알고리즘

15 Dec 2023

java

라빈 카프 알고리즘은 문자열 검색을 위해 사용되는 효율적인 해싱 기법 중 하나입니다. 이 알고리즘은 문자열을 숫자로 변환하여 두 문자열이 일치하는지를 빠르게 확인할 수 있습니다. 이번에는 자바를 활용하여 라빈 카프 알고리즘을 구현하는 방법에 대해 알아보겠습니다.

라빈 카프 알고리즘 구현하기

라빈 카프 알고리즘을 구현하기 위해 다음과 같은 단계를 따릅니다:

패턴과 텍스트의 해싱: 먼저 패턴과 텍스트를 해싱하여 숫자로 변환합니다.
패턴과 텍스트 비교: 해싱된 패턴과 텍스트를 비교하여 일치 여부를 확인합니다.
- 일치하지 않는 경우, 다음 위치의 해싱 값으로 이동하여 다시 비교합니다.
- 일치하는 경우, 실제 문자열을 확인하여 일치 여부를 최종적으로 확인합니다.

아래는 간단한 자바 코드 예제입니다.

public class RabinKarpAlgorithm {
    private final static int d = 256; // 문자 집합의 크기

    static void search(String pattern, String text, int q) {
        int M = pattern.length();
        int N = text.length();
        int i, j;
        int p = 0; // 패턴의 해시 값
        int t = 0; // 텍스트의 처음 M 글자에 대한 해시 값
        int h = 1;

        for (i = 0; i < M - 1; i++)
            h = (h * d) % q;

        for (i = 0; i < M; i++) {
            p = (d * p + pattern.charAt(i)) % q;
            t = (d * t + text.charAt(i)) % q;
        }

        for (i = 0; i <= N - M; i++) {
            if (p == t) {
                for (j = 0; j < M; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j))
                        break;
                }
                if (j == M)
                    System.out.println("Pattern found at index " + i);
            }
            if (i < N - M) {
                t = (d * (t - text.charAt(i) * h) + text.charAt(i + M)) % q;
                if (t < 0)
                    t = (t + q);
            }
        }
    }
}

이 코드는 라빈 카프 알고리즘을 사용하여 주어진 텍스트에서 패턴을 검색하는 기본적인 방법을 보여줍니다.

마치며

이렇게 하여 자바를 활용하여 라빈 카프 알고리즘을 구현할 수 있습니다. 이 알고리즘은 문자열 검색에 효율적이며, 대용량 텍스트에서의 빠른 검색이 필요한 경우 유용하게 사용될 수 있습니다.

라빈 카프 알고리즘에 대해 더 알아보려면 라빈-카프 알고리즘 - 위키백과를 참고하시기 바랍니다.