Java에서 KMP 알고리즘을 구현하는 방법은 무엇입니까?

Illustration

kmp 알고리즘은 앞서 언급한 bm 알고리즘의 아이디어와 어느 정도 유사성을 가지고 있습니다. 앞서 언급했듯이 bm 알고리즘에는 좋은 접두사라는 개념이 있고, kmp에는 좋은 접두사라는 개념이 있습니다. 먼저 다음 예를 살펴보겠습니다.

위의 예를 관찰하면 이미 일치하는 abcde를 좋은 접두사라고 하며, a는 다음 bcde와 일치하지 않으므로 다시 비교할 필요가 없으며 e 바로 뒤에 슬라이드하면 됩니다.

좋은 접두사에 일치하는 문자가 있으면 어떻게 되나요?

위의 예를 관찰하세요. 이때 좋은 접두사 바로 뒤에 슬라이드하면 너무 많이 슬라이드되어 일치하는 하위 문자열을 놓칠 것입니다. 그렇다면 좋은 접두사를 기반으로 합리적인 슬라이딩을 어떻게 수행합니까?

사실 현재 좋은 접두사의 접두사와 접미사가 일치하는지 확인하고, 일치하는 가장 긴 길이를 찾아 직접 슬라이드하는 것입니다. 가장 긴 일치 길이를 두 번 이상 찾는 관점에서 배열을 먼저 초기화하고 현재 good 접두사 아래에 가장 긴 일치 길이를 저장할 수 있습니다. 이때 다음 배열이 나옵니다.

현재 좋은 접두사 아래에 있는 좋은 접두사와 접미사의 일치하는 가장 긴 하위 문자열 길이를 나타내는 다음 배열을 정의합니다. 이 가장 긴 일치 길이는 이 하위 문자열이 이전에 일치했으며 다시 일치할 필요가 없음을 의미합니다. . , 일치는 하위 문자열의 다음 문자부터 직접 시작됩니다.

next[i]를 계산할 때마다 모든 문자를 일치시켜야 하나요? 불필요한 비교를 줄이기 위해 next[i - 1]을 기반으로 추론할 수 있나요?

이 아이디어를 바탕으로 다음 단계를 살펴보겠습니다.

next[i - 1] = k - 1이라고 가정;

If modelStr[k] = modelStr[i] then next[i]=k

modelStr[k] != modelStr[i]이면 next[i] = next[i - 1]을 직접 결정할 수 있나요?

위의 예를 통해 next[i]!=next[i-1]임을 확실히 알 수 있으며, modelStr[k]!=modelStr[i]인 경우 이미 next[ 0],next를 알고 있습니다. [1]…next[i-1], next[i]를 뒤집는 방법은 무엇입니까?

modelStr[x…i]가 접두사와 접미사가 일치할 수 있는 가장 긴 접미사 하위 문자열이라고 가정하면 가장 긴 일치 접두사 하위 문자열은 modelStr[0…i-x]

가장 긴 일치 문자열을 찾으면 이전 문자열입니다. 두 번째로 긴 일치 문자열(현재 i 제외), 즉 modelStr[x...i-1]은 이전에 해결되었어야 하므로 접두사 하위 문자열을 가정하여 해결된 이 일치 문자열만 찾으면 됩니다. modelStr[0…i-x-1]이고 접미사 하위 문자열은 modelStr[x…i-1]이며 modelStr[i-x] == modelStr[i]입니다. 이 접두사 접미사 하위 문자열은 보조 접두사 하위 문자열 문자열에 현재 문자를 더한 것입니다. 가장 긴 일치하는 접두사 및 접미사 하위 문자열입니다.

코드 구현

우선 kmp 알고리즘에서 가장 중요한 다음 배열입니다. 이 배열은 kmp 알고리즘에서 특정 접두사가 ​​좋은 접두사, 즉 패턴 문자열 접두사를 일치시킴으로써 특정 기술을 사용하여 두 문자 이상을 앞으로 밀 수 있습니다. 자세한 내용은 이전 설명을 참조하세요. 어떤 접두어가 좋은지 미리 알 수 없고, 매칭 과정이 2회 이상이므로 처음에 초기화 메소드를 호출해 다음 배열을 초기화합니다.

1. 이전 문자의 가장 긴 접두사 하위 문자열의 다음 문자 == 현재 문자인 경우 이전 문자의 가장 긴 접두사 하위 문자열을 현재 문자에 ​​직접 추가할 수 있습니다.

2. 이전 문자를 찾아야 합니다. 기존의 가장 긴 접두사 하위 문자열의 다음 문자는 현재 하위 문자열과 같습니다. 그런 다음 현재 문자 하위 문자열의 가장 긴 접두사 접미사 하위 문자열을 설정합니다.

int[] next ;
    /**
     * 初始化next数组
     * @param modelStr
     */
    public void init(char[] modelStr) {
        //首先计算next数组
        //遍历modelStr，遍历到的字符与之前字符组成一个串
        next = new int[modelStr.length];
        int start = 0;
        while (start < modelStr.length) {
            next[start] = this.recursion(start, modelStr);
            ++ start;
        }
    }

    /**
     *
     * @param i 当前遍历到的字符
     * @return
     */
    private int recursion(int i, char[] modelStr) {
        //next记录的是个数，不是下标
        if (0 == i) {
            return 0;
        }
        int last = next[i -1];
        //没有匹配的,直接判断第一个是否匹配
        if (0 == last) {
            if (modelStr[last] == modelStr[i]) {
                return 1;
            }
            return 0;
        }
        //如果last不为0，有值，可以作为最长匹配的前缀
        if (modelStr[last] == modelStr[i]) {
            return next[i - 1] + 1;
        }
        //当next[i-1]对应的子串的下一个值与modelStr不匹配时，需要找到当前要找的最长匹配子串的次长子串
        //依据就是次长子串对应的子串的下一个字符==modelStr[i];
        int tempIndex = i;
        while (tempIndex > 0) {
            last = next[tempIndex - 1];
            //找到第一个下一个字符是当前字符的匹配子串
            if (modelStr[last] == modelStr[i]) {
                return last + 1;
            }
            -- tempIndex;
        }
        return 0;
    }

그런 다음 일치시킬 다음 배열을 사용하여 시작합니다. 첫 번째 문자. , 일치하지 않는 첫 번째 문자를 찾습니다. 이때 이전 문자가 모두 일치합니다. 다음으로 먼저 완전한 일치인지 판단하고, 그렇지 않으면 첫 번째 문자가 일치하지 않는지 판단합니다. 그러면 뒷면과 직접 일치하게 됩니다. 좋은 접두사가 있으면 이때 다음 배열이 사용됩니다. 다음 배열을 통해 현재 매칭이 어디서 시작될 수 있는지 알 수 있으며, 이전 배열과 일치할 필요는 없습니다.

아아아아

위 내용은 Java에서 KMP 알고리즘을 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!