日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

c++?KMP字符串匹配算法_C 語言

作者：按時吃早飯的ju ? 更新時間： 2022-03-26 編程語言

KMP算法簡介

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

????????本章以力扣?28. 實現 strStr()為例子進行講解。

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

????????說明：當?needle?是空字符串時，我們應當返回什么值呢？這是一個在面試中很好的問題。對于本題而言，當?needle?是空字符串時我們應當返回 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;
    }
};

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

前綴表

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

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

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

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

????????KMP算法的核心思想就是先求出匹配模板的next數組，再運用next數組進行字符串匹配。??

如何構造前綴表next數組

void get_next(int *next,string t){ //t為模板字符串
        //定義兩個指針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]){//前后綴相同，前綴指針前進一位
                prefix++; 
            }
            next[suffix]=prefix;//更新next數組，prefix走到哪說明就有多少的相同的前后綴
        }
    }

如何用next數組進行模板匹配

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

由此可見構造next數組的時間復雜度是О(m)，利用next數組進行匹配的時間復雜度是О(n)，總的時間復雜度是О(n+m)

總結

原文鏈接：https://blog.csdn.net/qq_41251638/article/details/122408042

欄目分類
最近更新