什么是KPM算法

Knuth-Morris-Pratt 字符串查找算法，簡稱為 “KMP算法”，常用于在一個文本串S內查找一個模式串P 的出現(xiàn)位置，這個算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年聯(lián)合發(fā)表，故取這3人的姓氏命名此算法。

KMP方法算法就利用之前判斷過信息，通過一個next數(shù)組，保存模式串中前后最長公共子序列的長度，每次回溯時，通過next數(shù)組找到，前面匹配過的位置，省去了大量的計算時間。

KPM的使用場景：模式串在文本串是否出現(xiàn)過，如果出現(xiàn)過，最早出現(xiàn)的位置

步驟

Ⅰ根據(jù)《最大長度表》部分匹配表（next）

對于P = p0 p1 ...pj-1 pj，尋找模式串P中長度最大且相等的前綴和后綴。如果存在p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj，那么在包含pj的模式串中有最大長度為k+1的相同前綴后綴。

舉個例子，如果給定的模式串為“abab”，那么它的各個子串的前綴后綴的公共元素的最大長度如下表格所示：

比如對于字符串aba來說，它有長度為1的相同前綴后綴a；而對于字符串abab來說，它有長度為2的相同前綴后綴ab（相同前綴后綴的長度為k + 1，k + 1 = 2）。

結論：最大前綴后綴元素長度所得到的數(shù)組就是我們所需要的 “部分匹配表”

尋找最長前綴后綴

如果給定的模式串是：“ABCDABD”，從左至右遍歷整個模式串，其各個子串的前綴后綴分別如下表格所示：

Ⅱ 根據(jù) 部分匹配表 進行匹配

匹配失配，j = next [j]，模式串向右移動的位數(shù)為：j - next[j]。換言之，當模式串的后綴pj-k pj-k+1, ..., pj-1跟文本串si-k si-k+1, ..., si-1匹配成功，但pj跟si匹配失敗時，因為next[j] = k，相當于在不包含pj的模式串中有最大長度為k 的相同前綴后綴，即p0 p1 ...pk-1 = pj-k pj-k+1...pj-1，故令j = next[j]，從而讓模式串右移j - next[j]位，使得模式串的前綴p0 p1, ..., pk-1對應著文本串si-k si-k+1, ..., si-1，而后讓pk跟si繼續(xù)匹配。如下圖所示：

KMP的next數(shù)組相當于告訴我們：

當模式串中的某個字符跟文本串中的某個字符匹配失配時，模式串下一步應該跳到哪個位置。如模式串中在j處的字符跟文本串在i處的字符匹配失配時，下一步用next [j]處的字符繼續(xù)跟文本串i 處的字符匹配，相當于模式串向右移動j - next[j]位。

代碼實現(xiàn)

字符串匹配問題：

有一個字符串 str1=““上海自來水來自海上””，和一個子串 str2=“自來水”。

現(xiàn)在要判斷str1是否含有str2, 如果存在，就返回第一次出現(xiàn)的位置, 如果沒有，則返回-1

static void Main(string[] args)
{
    string str1 = "上海自來水來自海上";
    string str2 = "自來水";
	
	// 得出 部分匹配表
    int[] next = KPMNext(str2);
    // 根據(jù) 得出的 部分匹配表的 next 數(shù)組進行匹配，
    int index = KPMSearch(str1, str2, next);
    
    Console.WriteLine(index);
}

/// <summary>
/// 獲取一個字符串的部分匹配值表
/// </summary>
/// <param name="dest"></param>
/// <returns></returns>
static int[] KPMNext(string dest)
{
    // 初始化 數(shù)組大小
    int[] next = new int[dest.Length];
    // 字符串長度為1，部分匹配值就為0
    next[0] = 0;
    for (int i = 1, j = 0; i < dest.Length; i++)
    {
        while (j > 0 && dest[i] != dest[j])
        {
            j = next[j - 1];
        }
        if (dest[i] == dest[j])
        {
            j++;
        }
        next[i] = j;
    }
    return next;
}

/// <summary>
/// kmp搜索
/// </summary>
/// <param name="str1">源字符串</param>
/// <param name="str2">子字符串</param>
/// <param name="next">部分匹配表</param>
/// <returns></returns>
static int KPMSearch(string str1, string str2, int[] next)
{
    for (int i = 0, j = 0; i < str1.Length; i++)
    {
        while (j > 0 && str1[i] != str2[j])
        {
            j = next[j - 1];
        }

        if (str1[i] == str2[j])
        {
            j++;
        }

        if (j == str2.Length)
        {
            return i - j + 1;
        }
    }
    return -1;
}

到此這篇關于C#利用KPM算法解決字符串匹配問題詳解的文章就介紹到這了,更多相關C# KPM字符串匹配內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論