c++ KMP子串查找算法怎么用

這篇文章主要介紹了c++ KMP子串查找算法怎么用的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇c++ KMP子串查找算法怎么用文章都會有所收獲，下面我們一起來看看吧。

        我們在之前學習了字符串類，那么查找字符串類的需求就隨之而來。如何在目標字符串 S 中，查找是否存在子串 P？

        我們大家最先能想到的肯定是樸素解法，何謂樸素解法呢？就是一個一個進行對比，如果比對不成功，便向后移一位。代碼如下

        那么此時的解法肯定不太好，因為它的時間復雜度為 O(m*n)。那么我們該如何對其進行優化呢？我們來看看下圖

        由上圖我們可以得出一個結論：因為 Pa ！=Pb 且 Pb == Sb；所以 Pa！+ Sb；因此，子串 p 右移 1 位是沒有意義的。接下來我們以示例字符串為例來進行分析說明，如下

        我們看到在第一步的時候，第 1 個字符就匹配失敗，然后我們直接右移 1 位；直至第 7 個字符匹配失敗，此時我們通過肉眼觀察可知，右移 4 位是最好的；接下來在匹配到第 3 個字符的時候又失敗了，通過肉眼觀察可知，右移 2 為是最好的；后面以此類推。

        那么我們是否有什么發現呢？只要我們能知道需要右移幾位，我們便可以輕易的得出結論。那么這塊就有前人已經發現了規律，我們只需掌握這個方法即可輕易的解決問題。那么偉大的發現是什么呢？在匹配失敗時的右移位數與子串本身相關與目標串無關；移動位數 = 已匹配的字符數 - 對應的部分匹配值；任意子串都存在一個唯一的部分匹配表。

        下來我們來看看一個部分匹配表的示例，如下

        那么問題來了，這個部分匹配表是如何得到的呢？首先我們來介紹兩個概念：前綴和后綴。前綴是指除了最后一個字符以外，一個字符串的全部頭部組合；后綴是指除了第一個字符以外，一個字符串的全部尾部組合。那么部分匹配值便是前綴和后綴最長共有元素的長度，我們以字符串 “ABCDABD” 為例來進行分析，如下圖所示

        我們看到在第一個字符 A 的時候，它的交集為空，因此匹配值為 0；在前兩個字符時，同樣為空，因此匹配值也為空；直至第5個字符時，交集為 A，因此它的匹配值為 1；第 6 個字符時，交集為 AB，因此此時的匹配值為 2；最后一個字符時，交集為空，因此匹配值為 0。

        那么我們知道了如何手動的求解部分匹配值，那么如何在程序中編程產生部分匹配表呢？

        實現關鍵：

        1、PMMT[1] = 0（下標為 0 的元素匹配值為 0）

        2、從 2 個字符開始遞推（從下標為 1 的字符開始遞推）

        3、假設 PMT[n] = PMT[n-1] + 1（最長共有元素的長度）

        4、當假設不成立，PMT[n] 在 PMT[n-1] 的基礎上減小

        下來我們來實現部分匹配表的程序，代碼如下

#include <iostream>
#include <cstring>
#include "DTString.h"

using namespace std;
using namespace DTLib;

int* make_pmt(const char* p)    // O(n)
{
    int len = strlen(p);
    int* ret = static_cast<int*>(malloc(sizeof(int) * len));

    if( ret != NULL )
    {
        int ll = 0;

        ret[0] = 0;

        for(int i=1; i<len; i++)
        {
            while ( (ll > 0) && (p[ll] != p[i]) )
            {
                ll = ret[ll-1];
            }

            if( p[ll] == p[i] )
            {
                ll++;
            }

            ret[i] = ll;
        }
    }

    return ret;
}

int main()
{
    int* pmt = make_pmt("ABCDABD");

    for(int i=0; i<strlen("ABCDABD"); i++)
    {
        cout << i << " : " << pmt[i] << endl;
    }

    return 0;
}

        我們來看看結果是否和我們上面推導的是一樣的？

        我們看到結果是 0 0 0 0 1 2 0，和我們上面手動推導出來的結果是一致的，因此這個部分匹配表的代碼編寫是正確的。下來我們就來看看部分匹配表的使用（KMP 算法）：下標 j 處匹配失敗 --> 前 j 位匹配成功 --> 查表 PMT[j-1] --> 右移位數 j-PMT[j-1]。如下圖所示

        因為 s[i] != p[j]， 所以查表可知，LL= PMT[j-1]。于是乎，右移，i 的值不變，j 的值改變，j = j - (j-LL) = LL = PMT[j-1]。

        下來我們來看看 KMP 子串查找算法的具體實現，如下

#include <iostream>
#include <cstring>
#include "DTString.h"

using namespace std;
using namespace DTLib;

int* make_pmt(const char* p)    // O(n)
{
    int len = strlen(p);
    int* ret = static_cast<int*>(malloc(sizeof(int) * len));

    if( ret != NULL )
    {
        int ll = 0;

        ret[0] = 0;

        for(int i=1; i<len; i++)
        {
            while ( (ll > 0) && (p[ll] != p[i]) )
            {
                ll = ret[ll-1];
            }

            if( p[ll] == p[i] )
            {
                ll++;
            }

            ret[i] = ll;
        }
    }

    return ret;
}

int kmp(const char* s, const char* p)   // O(m) + O(n) ==> O(m+n)
{
    int ret = -1;
    int sl = strlen(s);
    int pl = strlen(p);
    int* pmt = make_pmt(p);

    if( (pmt != NULL) && (0 < pl) && (pl <= sl) )
    {
        for(int i=0, j=0; i<sl; i++)
        {
            while( (j > 0) && (s[i] != p[j]) )
            {
                j = pmt[j-1];
            }

            if( s[i] == p[j] )
            {
                j++;
            }

            if( j == pl )
            {
                ret = i + 1 - pl;
                break;
            }
        }
    }

    free(pmt);

    return ret;
}

int main()
{
    cout << kmp("abcde", "cd") << endl;
    cout << kmp("ababax", "d") << endl;

    return 0;
}

        我們來看看結果，如下

關于“c++ KMP子串查找算法怎么用”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“c++ KMP子串查找算法怎么用”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。