【算法】kmp

Bertha 。 2024-03-27 16:00 1阅读 0赞

## KMP算法 ##

### 名称由来 ###

是由发明这个算法的三个科学家的名称首字母组成

### 作用 ###

用于字符串的匹配问题

### 举例说明 ###

字符串 aabaabaaf  
模式串 aabaaf

#### 传统匹配方法 ####

##### 第一步 #####

aabaabaaf  
aabaaf

此时，b和f不一致，则把模式串从头和文本串的第二个字符开始比

##### 第二步 #####

aabaabaaf  
\_aabaaf

。。。。。以此类推，知道找到相同的或者结束

#### KMP算法 ####

##### 第一步 #####

aabaabaaf  
aabaaf

此时，b和f不一致，但是b和f前面的子串 aabaa  
拥有最长相等前后缀2，因此可以跳过前两个字符 aa  
，直接用文本串的 b 和 模式串的第三个字符继续比较

##### 第二步 #####

aabaabaaf  
\_\_\_aabaaf

。。。。。以此类推，知道找到相同的或者结束

## 最长相等前后缀 ##

定义，以aabaa 为例  
前缀：不包括最后一个字符  
a  
aa  
aab  
aaba

后缀：不包括第一个字符  
a  
aa  
baa  
abaa

最长相等前后缀就是 aa 长度为2

每一个字符串都对应一个最长相等前后缀表  
aabaa  
next\[5\] 0 1 0 1 2

## 相关题目 ##

[28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）][28. _ - _LeetCode]

class Solution {
        
        /**
         * KMP算法
         * @param haystack
         * @param needle
         * @return
         */
        public int strStr(String haystack, String needle) {
        
            //特判 1 <= haystack.length, needle.length <= 104
            if(needle.length()==0) return 0;
            //求next数组
            int [] next=new int[needle.length()];//回退数组，要回退的位置
            next[0]=0;
            int j=0;//前缀末尾，同时兼具最长相等前缀和后缀的功能
            for (int i = 1; i < needle.length(); i++) {
        //i是后缀末尾
                //不相等，循环回退
                while(j>0&&needle.charAt(i)!=needle.charAt(j)){
        
                    j=next[j-1];
                }
                //相等
                if(needle.charAt(i)==needle.charAt(j)){
        
                    j++;
                }
                //更新
                next[i]=j;
            }
            //匹配haystack
            int k = 0;
            for (int i = 0; i < haystack.length(); i++) {
        
                while (k > 0 && needle.charAt(k) != haystack.charAt(i))
                    k = next[k - 1];
                if (needle.charAt(k) == haystack.charAt(i))
                    k++;
                if (k == needle.length())
                    return i - needle.length() + 1;
            }
            return -1;
        }
    }

[28. _ - _LeetCode]: https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/