c++ KMP字符串匹配算法

更新時(shí)間：2022年01月11日 08:38:32 作者：按時(shí)吃早飯的ju

大家好，本篇文章主要講的是c++ KMP字符串匹配算法，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下

KMP算法簡介

KMP算法(Knuth-Morris-Pratt 算法)是一個(gè)著名的字符串匹配算法，它主要的思想是當(dāng)出現(xiàn)字符串不匹配時(shí)，可以知道一部分之前已經(jīng)匹配的文本內(nèi)容，可以利用這些信息避免從頭再去做匹配。

本章以力扣 28. 實(shí)現(xiàn) strStr()為例子進(jìn)行講解。

力扣28.實(shí)現(xiàn)strStr()函數(shù)：給你兩個(gè)字符串 haystack 和 needle ，請你在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置（下標(biāo)從 0 開始）。如果不存在，則返回 -1 。

說明：當(dāng) needle 是空字符串時(shí)，我們應(yīng)當(dāng)返回什么值呢？這是一個(gè)在面試中很好的問題。對于本題而言，當(dāng) needle 是空字符串時(shí)我們應(yīng)當(dāng)返回 0 。

示例 1：輸入：haystack = "hello", needle = "ll" 輸出：2

此題若用暴力解法代碼如下：

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n=haystack.size(),m=needle.size();
        if(m==0) return 0;
        for(int i=0;i<n;i++){
            if(haystack[i]==needle[0]){
                for(int j=0;j<m;j++){
                    if(haystack[i+j]!=needle[j])
                        break;
                    if(j==m-1) return i;
                }
            }
        }
        return -1;
    }
};

可見暴力匹配過程中實(shí)現(xiàn)的是一個(gè)雙層循環(huán)，那么算法的時(shí)間復(fù)雜度較高，為О(n*m)，然而KMP的算法時(shí)間復(fù)雜度僅為О(n+m)，其算法性能明顯提高，具體時(shí)間復(fù)雜度計(jì)算方法后面介紹。

前綴表

KMP算法中一個(gè)重要的概念就是前綴表（prefix table），并用一維數(shù)組 next 記錄前綴信息實(shí)際上next數(shù)組就是一個(gè)前綴表。

了解前綴表我們首先需要了解前綴和后綴的區(qū)別，此處的前綴是指不包含最后一個(gè)字符的所有以第一個(gè)字符開頭的連續(xù)子串，后綴是指不包含第一個(gè)字符的所有以最后一個(gè)字符結(jié)尾的連續(xù)子串。比如字符串“abac”的前綴有“a”, "ab”, "aba”，字符串“abac”的后綴有“c”,"ac”，"bac”。

前綴表第 i 個(gè)位置存的值 next[i] 代表[0,i]這個(gè)字符串最長的相同前后綴的長度，比如字符串“abbc”的 next[3]為 0 ,next[2]為 1 ("aba”的前綴有“a”, "ab”，后綴有“a”,"ba”)。

前綴表的作用是用來記錄了模板串與主串(文本串)不匹配的時(shí)候，模板串應(yīng)該從哪里開始重新匹配。

KMP算法的核心思想就是先求出匹配模板的next數(shù)組，再運(yùn)用next數(shù)組進(jìn)行字符串匹配。

如何構(gòu)造前綴表next數(shù)組

void get_next(int *next,string t){ //t為模板字符串
        //定義兩個(gè)指針prefix和suffix，prefix指向前綴起始位置，suffix指向后綴起始位置
        int prefix=0;
        next[prefix]=0;
        for(int suffix=1;suffix<t.size();suffix++){
            while(prefix>0 && t[suffix]!=t[prefix]){//前后綴不相同，前綴指針向前回退
                prefix=next[prefix-1];
            }
            if(t[suffix]==t[prefix]){//前后綴相同，前綴指針前進(jìn)一位
                prefix++; 
            }
            next[suffix]=prefix;//更新next數(shù)組，prefix走到哪說明就有多少的相同的前后綴
        }
    }

如何用next數(shù)組進(jìn)行模板匹配

int strStr(string haystack, string needle) {
        if(needle.size()==0) return 0;
        int next[needle.size()];
        get_next(next,needle);
        int j=0;
        //定義兩個(gè)下標(biāo)j指向模版串起始位置，i指向文本串起始位置
        for(int i=0;i<haystack.size();i++){
            while(j>0 && haystack[i]!=needle[j]){ //模版串j位置和文本串i位置不相同，j利用next數(shù)組回退到上一個(gè)相同的位置繼續(xù)匹配
                j=next[j-1];
            }
            if(haystack[i]==needle[j]){  //模版串j位置和文本串i位置相同
                j++;
            }
            if(j==needle.size()){  //找到匹配的字符串
                return (i-needle.size()+1); //返回匹配的字符串起始位置
            }
        }
        return -1;
    }

由此可見構(gòu)造next數(shù)組的時(shí)間復(fù)雜度是О(m)，利用next數(shù)組進(jìn)行匹配的時(shí)間復(fù)雜度是О(n)，總的時(shí)間復(fù)雜度是О(n+m)