Java를 사용하여 문자열 일치 알고리즘을 구현하는 방법

Java를 사용하여 문자열 일치 알고리즘을 구현하는 방법

소개:
문자열 일치 알고리즘은 컴퓨터 분야에서 흔히 발생하는 문제로, 주 문자열에서 특정 패턴 문자열의 발생 위치를 찾는 데 사용됩니다. 실제 개발에서는 텍스트 편집기의 검색 기능, 검색 엔진의 키워드 매칭 등 문자열 매칭이 필요한 경우가 많습니다. 이 기사에서는 몇 가지 일반적인 문자열 일치 알고리즘을 소개하고 해당 Java 코드 예제를 제공합니다.

1. 무차별 매칭 알고리즘
순진 매칭 알고리즘이라고도 알려진 무차별 매칭 알고리즘은 가장 기본적인 문자열 매칭 알고리즘입니다. 그 원리는 매우 간단합니다. 즉, 기본 문자열의 모든 위치에서 시작하여 일치하지 않는 문자가 나타나거나 일치하는 문자가 성공적으로 발견될 때까지 문자별로 패턴 문자열을 비교합니다.

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

public class BruteForceMatcher {
    public int match(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;
    }
}

2. KMP 알고리즘
KMP 알고리즘은 불필요한 문자 비교를 피하기 위해 패턴 문자열의 부분 일치 정보를 사용하는 효율적인 문자열 일치 알고리즘입니다. KMP 알고리즘의 핵심은 패턴 문자열의 각 위치에서 가장 긴 공통 접미사의 길이를 기록하기 위해 다음 배열을 구성하는 것입니다.

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

public class KMPMatcher {
    public int match(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] next = getNext(pattern);
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == m) {
            return i - j;
        } else {
            return -1;
        }
    }

    private int[] getNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = -1;
        int i = 0, j = -1;
        while (i < m - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (pattern.charAt(i) != pattern.charAt(j)) {
                    next[i] = j;
                } else {
                    next[i] = next[j];
                }
            } else {
                j = next[j];
            }
        }
        return next;
    }
}

3. Boyer-Moore 알고리즘
Boyer-Moore 알고리즘은 패턴 문자열의 문자 분포 정보와 역방향 이동 규칙을 활용하는 효율적인 문자열 일치 알고리즘입니다.

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

public class BMMatcher {
    public int match(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] bmBc = preBmBc(pattern);
        int[] bmGs = preBmGs(pattern);
        int j = 0;
        while (j <= n - m) {
            int i;
            for (i = m - 1; i >= 0 && pattern.charAt(i) == text.charAt(i + j); i--);
            if (i < 0) {
                return j;
            } else {
                j += Math.max(bmGs[i], bmBc[text.charAt(i + j)] - m + 1 + i);
            }
        }
        return -1;
    }

    private int[] preBmBc(String pattern) {
        int[] bmBc = new int[256];
        int m = pattern.length();
        for (int i = 0; i < 256; i++) {
            bmBc[i] = m;
        }
        for (int i = 0; i < m - 1; i++) {
            bmBc[pattern.charAt(i)] = m - 1 - i;
        }
        return bmBc;
    }

    private int[] preBmGs(String pattern) {
        int m = pattern.length();
        int[] bmGs = new int[m];
        int i = m - 1, j = m;
        bmGs[m - 1] = m;
        while (i >= 0) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                bmGs[--i] = --j;
            } else {
                j = m - 1 - i;
                while (j < m && pattern.charAt(m - 1 - j) == pattern.charAt(j)) {
                    j++;
                }
                bmGs[i] = j;
            }
        }
        return bmGs;
    }
}

결론:
위는 무차별 대입 알고리즘, KMP 알고리즘, Boyer-Moore 알고리즘인 세 가지 일반적인 문자열 매칭 알고리즘의 코드 예제입니다. 실제 적용에서는 일치 효율성을 향상시키기 위해 특정 요구에 따라 적절한 알고리즘을 선택할 수 있습니다.

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