如何實作C#中的KMP演算法

如何實作C#中的KMP演算法

KMP（Knuth-Morris-Pratt）演算法，是一種高效的字串比對演算法，用於在文字串中尋找模式串的位置。它的核心思想是利用已匹配的部分訊息，避免不必要的比較。

實作KMP演算法的關鍵是建立一個部分匹配表（Partial Match Table），也叫做next陣列。這個陣列記錄了模式字串中每個前綴子字串的最長可匹配後綴子字串的長度。

下面是C#中實作KMP演算法的具體步驟與程式碼範例：

步驟一：建構部分符合表

1. 定義一個大小為模式串長的整數陣列next，並初始化next[0] = -1。
2. 定義兩個指標 i 和 j，初始值分別為 0 和 -1。
3. 判斷i 是否達到模式字串的結尾，若沒有則執行下列步驟：
   a. 若j 等於-1 或目前字元和指標j 對應的字元相等，則i 和j 同時後移，並將next[i] = j。
   b. 否則，將指標 j 移到 next[j] 的位置，繼續進行比對。
4. 傳回建立好的部分符合表 next。

以下是如何實現上述步驟的程式碼：

private int[] BuildNext(string pattern)
{
    int[] next = new int[pattern.Length];
    next[0] = -1;
    int i = 0, j = -1;
    
    while (i < pattern.Length - 1)
    {
        if (j == -1 || pattern[i] == pattern[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    
    return next;
}

步驟二：使用部分匹配表進行匹配

1. 定義兩個指標i 和j ，分別指向文字串和模式串的起始位置。
2. 判斷 i 和 j 是否達到結尾，若沒有則執行下列步驟：
   a. 若 j 等於 -1 或目前字元和指標 j 對應的字元相等，則 i 和 j 同時後移。
   b. 否則，將指標 j 移到 next[j] 的位置，繼續進行比對。
3. 若指標 j 指向模式字串的結尾，表示符合成功，傳回起始位置在文字字串中的索引。
4. 若符合失敗，則回傳 -1。

以下是如何實現上述步驟的程式碼：

private int KMP(string text, string pattern)
{
    int[] next = BuildNext(pattern);
    int i = 0, j = 0;
    
    while (i < text.Length && j < pattern.Length)
    {
        if (j == -1 || text[i] == pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    
    if (j == pattern.Length)
    {
        return i - j;
    }
    
    return -1;
}

透過呼叫 KMP 方法，並傳入文字串和模式串，即可獲得匹配結果。

以上就是如何在C#中實作KMP演算法的步驟和程式碼範例。透過利用部分匹配表，KMP演算法能夠有效地提高字串匹配的效率，特別是在處理大文本串和長模式字串時，具有較好的效能表現。

以上是如何實作C#中的KMP演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！