Java를 사용하여 Boyer-Moore 알고리즘을 구현하는 방법

Java를 사용하여 Boyer-Moore 알고리즘을 구현하는 방법

소개:
컴퓨터 과학에서 문자열 일치는 일반적인 작업입니다. 문자열 매칭 알고리즘은 이 문제를 해결하는 열쇠입니다. 효율적인 문자열 일치 알고리즘 중 하나는 Boyer-Moore 알고리즘입니다. 이 기사에서는 Java 언어를 사용하여 이 알고리즘을 구현하는 방법을 소개하고 특정 코드 예제를 첨부합니다.

Boyer-Moore 알고리즘의 원리:
Boyer-Moore 알고리즘은 패턴 문자열을 전처리하고 좋은 접미사 규칙과 잘못된 문자 규칙을 결합하여 일치를 완료하는 다중 패턴 문자열 일치 알고리즘입니다. 패턴 문자열과 일치 대상 문자열 간의 일치 과정에서 일치하지 않는 문자를 최대한 건너뛰어 일치 효율성을 높이는 것이 핵심 아이디어입니다.

구체적인 구현 단계:

1. 패턴 문자열 전처리:
   먼저 패턴 문자열을 전처리하고 두 개의 배열, 즉 잘못된 문자 배열과 좋은 접미사 배열을 생성해야 합니다.

   • 잘못된 문자 배열: 패턴 문자열에서 각 문자의 가장 오른쪽 위치를 저장합니다.
   • 좋은 접미사 배열: 패턴 문자열의 접미사 하위 문자열이 가장 오른쪽에 나타나는 위치를 패턴 문자열에 기록하고, 이 하위 문자열이 패턴 문자열의 접두사와 일치하는지 기록합니다.

2. 매칭 과정:
   매칭 과정에서는 매칭할 문자열의 끝에서부터 앞으로 매칭을 시작합니다.

   • 먼저 패턴 문자열의 끝 부분을 일치시키려는 문자열의 끝 부분에 맞춰서 일치시켜 보세요.
   • 일치가 성공하면 일치의 시작 위치가 반환되고, 그렇지 않으면 잘못된 문자와 좋은 접미사 규칙에 따라 패턴 문자열의 위치가 이동되어 일치가 계속됩니다.

구체적인 코드는 다음과 같습니다.

import java.util.Arrays;

public class BoyerMoore {

    private static final int NO_OF_CHARS = 256;

    private int[] badCharShift;
    private int[] suffixShift;
    private boolean[] goodSuffix;

    public void preProcessPattern(String pattern) {
        int m = pattern.length();
        // 初始化数组
        badCharShift = new int[NO_OF_CHARS];
        suffixShift = new int[m + 1];
        goodSuffix = new boolean[m + 1];

        Arrays.fill(badCharShift, -1);
        for (int i = 0; i < m; i++) {
            badCharShift[pattern.charAt(i)] = i;
        }

        int f = 0;
        int g = 0;
        suffixShift[m] = m + 1;

        for (int i = m - 1; i >= 0; i--) {
            if (i > f && suffixShift[i + m - f] < i - f) {
                suffixShift[i] = suffixShift[i + m - f];
            } else {
                if (i < f) {
                    f = i;
                }
                g = i;
                while (f >= 0 && pattern.charAt(f) == pattern.charAt(f + m - g)) {
                    f--;
                }
                suffixShift[i] = g - f;
            }
        }

        for (int i = 0; i < m; i++) {
            goodSuffix[i] = suffixShift[i] > m - i;
        }
    }

    public int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int i = 0;

        while (i <= n - m) {
            int j = m - 1;
            while (j >= 0 && pattern.charAt(j) == text.charAt(i + j)) {
                j--;
            }
            if (j < 0) {
                return i; // 匹配成功，返回匹配位置
            } else {
                i += Math.max(goodSuffix[j + 1], j - badCharShift[text.charAt(i + j)]);
            }
        }
        return -1; // 未匹配成功，返回-1
    }

    public static void main(String[] args) {
        BoyerMoore bm = new BoyerMoore();
        String text = "This is a test";
        String pattern = "test";
        bm.preProcessPattern(pattern);
        int index = bm.search(text, pattern);
        if (index != -1) {
            System.out.println("Pattern found at index: " + index);
        } else {
            System.out.println("Pattern not found");
        }
    }
}

요약:
이 글에서는 Java 언어를 사용하여 Boyer-Moore 알고리즘을 구현하는 방법을 소개하고, 구체적인 코드 예제를 통해 알고리즘의 사용법을 보여줍니다. Boyer-Moore 알고리즘은 문자열 일치 분야에서 효율성이 높고 폭넓게 적용됩니다. 좋은 접미사와 잘못된 문자 규칙을 합리적으로 활용하면 문자열 일치의 효율성이 크게 향상될 수 있습니다. 이 글이 Boyer-Moore 알고리즘을 이해하고 실습하는 데 도움이 되기를 바랍니다.

위 내용은 Java를 사용하여 Boyer-Moore 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!