What is the implementation method of KMP algorithm in Java?

Illustration

The kmp algorithm has a certain similarity with the idea of ​​the bm algorithm mentioned before. As mentioned before, there is the concept of a good suffix in the bm algorithm, and there is a concept of a good prefix in kmp. What is a good prefix? Let's first look at the following example.

Observe the above example, the already matched abcde is called a good prefix, a does not match the following bcde, so there is no need to compare again, slide directly after e That’s it.

What if there are matching characters in the good prefix?

Observe the above example, if we slide directly after the good prefix at this time, we will slide too much and miss the matching substring. So how do we perform reasonable sliding based on good prefixes?

In fact, it is to check whether the prefix and suffix of the current good prefix match, find the longest matching length, and slide directly. In view of finding the longest matching length more than once, we can initialize an array first and save the longest matching length under the current good prefix. At this time, our next array will come out.

We define a next array, which represents the length of the longest matching substring of the prefix and suffix of the good prefix under the current good prefix. This longest matching length means that this substring has been matched before, not It is necessary to match again, starting directly from the next character of the substring.

Do we need to match every character every time we calculate next[i]? Can we deduce based on next[i - 1] to reduce unnecessary comparisons? .

With this idea, let’s take a look at the following steps:

Assume next[i - 1] = k - 1;

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

##If modelStr[k] != modelStr[i], can we directly determine next[i] = next[i - 1]?

Through the above example, we can clearly see that next[i]!=next[i-1], then modelStr[k]!=modelStr At [i], we already know next[0], next[1]...next[i-1], how to overturn next[i]?

Assume that modelStr[x…i] is the longest suffix substring that the prefix and suffix can match, then the longest matching prefix substring is modelStr[0…i-x]

When we find the longest matching string, its previous second-longest matching string (excluding the current i), that is, modelStr[x…i-1] should have been solved before. , so we only need to find this certain matching string that has been solved. Assume that the prefix substring is modelStr[0…i-x-1], the suffix substring is modelStr[x…i-1], and modelStr[i-x] == modelStr [i], this prefix and suffix substring is the secondary prefix substring, plus the current character is the longest matching prefix and suffix substring.

Code implementation

First of all, the most important next array in the kmp algorithm. This array marks the number of longest prefix and suffix matching substring characters up to the current subscript. In the kmp algorithm, if If a certain prefix is ​​a good prefix, that is, it matches the pattern string prefix, we can use certain techniques to slide more than one character forward. See the previous explanation for details. We don't know in advance which are good prefixes, and the matching process is more than once, so we call an initialization method at the beginning to initialize the next array.

1. If the next character of the longest prefix substring of the previous character == the current character, the longest prefix substring of the previous character can be directly added to the current character

2 .If not equal, you need to find the next character of the previously existing longest prefix substring that is equal to the current substring, and then set the longest prefix suffix substring of the current character substring

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;
    }

and then start using the next array Match, start matching from the first character, and find the first unmatched character. At this time, all the previous ones are matched. Next, first judge whether it is a complete match. If it is a direct return, if not, judge whether the first character is matched. If one does not match, it will match directly to the next one. If there is a good prefix, the next array is used at this time. Through the next array, we know where the current matching can start, and there is no need to match the previous ones.

public int kmp(char[] mainStr, char[] modelStr) {
        //开始进行匹配
        int i = 0, j = 0;
        while (i + modelStr.length <= mainStr.length) {
            while (j < modelStr.length) {
                //找到第一个不匹配的位置
                if (modelStr[j] != mainStr[i]) {
                    break;
                }
                ++ i;
                ++ j;
            }
            if (j == modelStr.length) {
                //证明完全匹配
                return i - j;
            }
            //走到这里找到的是第一个不匹配的位置
            if (j == 0) {
                ++ i;
                continue;
            }
            //从好前缀后一个匹配
            j = next[j - 1];
        }
        return -1;
    }

The above is the detailed content of What is the implementation method of KMP algorithm in Java?. For more information, please follow other related articles on the PHP Chinese website!