什么是KPM算法

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

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

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

步驟

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

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

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

比如對(duì)于字符串a(chǎn)ba來(lái)說(shuō)，它有長(zhǎng)度為1的相同前綴后綴a；而對(duì)于字符串a(chǎn)bab來(lái)說(shuō)，它有長(zhǎng)度為2的相同前綴后綴ab（相同前綴后綴的長(zhǎng)度為k + 1，k + 1 = 2）。

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

尋找最長(zhǎng)前綴后綴

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

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

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

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

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

代碼實(shí)現(xiàn)

字符串匹配問(wèn)題：

有一個(gè)字符串 str1=““上海自來(lái)水來(lái)自海上””，和一個(gè)子串 str2=“自來(lái)水”。

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

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

/// <summary>
/// 獲取一個(gè)字符串的部分匹配值表
/// </summary>
/// <param name="dest"></param>
/// <returns></returns>
static int[] KPMNext(string dest)
{
    // 初始化 數(shù)組大小
    int[] next = new int[dest.Length];
    // 字符串長(zhǎng)度為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;
}

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

最新評(píng)論