資料結構_KMP字元串比對算法(C語言)

資料結構總目錄

KMP

• KMP字元串比對算法
• • 1. 簡單模式比對算法的正向比對
  • • 1.1 圖文解析
    • 1.2 源代碼
    • 1.3 測試結果
  • 2. 簡單模式比對算法的反向比對
  • • 2.1 圖文解析
    • 2.2 源代碼
    • 2.3 測試結果
  • 3. KMP字元串比對算法
  • • 3.1 圖文解析
    • 3.2 源代碼
    • 3.3 測試結果

KMP字元串比對算法

KMP算法是一種對簡單模式比對算法進行改進的字元串比對算法

由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，是以人們稱它為克努特—莫裡斯—普拉特操作（簡稱KMP算法）。

KMP算法的核心是利用比對失敗後的資訊，盡量減少模式串與主串的比對次數以達到快速比對的目的。

1. 簡單模式比對算法的正向比對

1.1 圖文解析

存在主字元串 mainStr 和需要比對的子串 subStr

若發生比對失敗，主串指針回退到起點的下一個位置，子串指針則從頭開始

1.2 源代碼

#include <stdio.h>

int MatchSearch(char *mainStr, char *subStr, int len1, int len2)
{
    int i = 0, j = 0;
    while (i < len1 && j < len2)
    {
        if (mainStr[i] == subStr[j])
        {
        	// 向後比對
            ++i;
            ++j;
        }
        else
        {
            // 主串指針回退到起點的下一個位置
            i = i - j + 1;
            // 子串指針從頭開始
            j = 0;
        }
    }
    return j >= len2 ? i - len2 : -1;
}
 

int main()
{
    char mainStr[10] = "ababaababc";
    char subStr[5] = "ababc";

    int pos = MatchSearch(mainStr, subStr, 10, 5);
    if (pos > -1)
    {
        printf("比對成功: %d\n", pos);
    }
    else
    {
        printf("比對失敗!\n");
    }
    
    return 0;
}
           

1.3 測試結果

2. 簡單模式比對算法的反向比對

2.1 圖文解析

觀察下圖的簡單比對過程，我們可以發現

其實在a和c發生不比對時，就可以判斷出主串中[0，4]（ababa）與子串（abaac）不比對了

于是我們可以直接從子串結尾處開始進行判斷

若發生不比對，則回退到結尾處的下一個位置

若比對成功，則可以反向進行比對

2.2 源代碼

#include <stdio.h>

int MatchSearch(char *mainStr, char *subStr, int len1, int len2)
{
    int i = len2 - 1, j = len2 - 1;
    // 從子串的最後一個位置開始查詢
    while (i < len1 && j >= 0)
    {       
    	// 向前比對
        if (mainStr[i] == subStr[j])
        {
            --i;
            --j; 
        }
        else
        {
            // 主串指針回退到開始位置的下一個位置
            i = i + (len2 - 1 - j) + 1;
            // 子串指針結尾開始
            j = len2 - 1;
            flag = i - len2 + 1;
        }
    }
    return j < 0 ? i + 1 : -1;
}
 

int main()
{
    char mainStr[10] = "ababaababc";
    char subStr[5] = "ababc";

    int pos = MatchSearch(mainStr, subStr, 10, 5);
    if (pos > -1)
    {
        printf("比對成功: %d\n", pos);
    }
    else
    {
        printf("比對失敗!\n");
    }
    
    return 0;
}
           

2.3 測試結果

3. KMP字元串比對算法

3.1 圖文解析

一、觀察如下圖，我們發現在發生在不比對位置之前的字元串【abab】是相同的，且存在最大相同前字尾序列【ab】

那麼我們便可以根據最大相同字首序列進行快速移動子串，如下圖：

二、于是我們可以根據最大相同前字尾序列，将下次快速移動的位置存儲在一個輔助數組中next【】中

代表當subStr[i]與主串發生不比對時，可以根據next[i]快速定位下次比對的位置為j

可以了解為簡單模式比對算法的反向比對過程中，進行反向搜尋的快速定位

3.2 源代碼

#include <stdio.h>


void InitNext(int *next, char *subStr, int len)
{
    next[0] = -1;
    // (字尾結束下标 i) 和 (字首結束下标 j)
    int i = 0, j = -1;
    while (i < len)
    {
        if (j == -1 || subStr[i] == subStr[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            // 重新定位相同字首、字尾的位置
            j = next[j];
        }
    }
}

int KMPSearch(char *mainStr, char *subStr, int len1, int len2)
{
    
    int next[len2];
    int i = 0, j = 0;
    
    // 初始化next數組
    InitNext(next, subStr, len2);
    
    // 根據next數組進行快速定位查找
    while (i < len1 && j < len2)
    {       
        if (j == -1 || mainStr[i] == subStr[j])
        {
            i++;
            j++;  
        }
        else
        {
            // 根據next數組快速定位下一個比對的子串位置
            j = next[j]; 
        }
    }
    return j >= len2 ? i - len2 : -1;
}
 
int main()
{
    char mainStr[10] = "ababaababc";
    char subStr[5] = "ababc";

    int pos = KMPSearch(mainStr, subStr, 10, 5);
    if (pos > -1)
    {
        printf("比對成功: %d\n", pos);
    }
    else
    {
        printf("比對失敗!\n");
    }
    
    return 0;
}
           

3.3 測試結果