資料結構實機實驗報告3——KMP演算法用於字串搜尋

2023-12-12 2023-12-12

實驗目的：

本實驗旨在分析和測試KMP算法的實現，並研究其在字串搜尋中的應用。

實驗內容：

a 問題分析：

如何構建最長前綴後綴匹配表（LPS陣列）以提高搜尋效率？
如何在文本字串中執行匹配，利用LPS陣列來避免不必要的字元比較？
如何設計算法以實現模式字串的搜尋？

b 算法設計：

KMP算法的設計包括以下關鍵步驟：

構建LPS陣列：使用computeLPSArray函數來計算模式字串的LPS陣列，該陣列指示了模式字串中每個位置的前綴和後綴的最長匹配長度。
在文本中執行匹配：使用KMPSearch函數，該函數在文本字串中執行模式字串的匹配。它使用LPS陣列來智能地回溯，以提高搜尋效率。

c 資料結構設計：

在這次實驗中，我使用了以下資料結構：

字串：用於表示文本字串和模式字串。
向量（vector）：用於儲存LPS陣列。
整數變數：用於表示匹配過程中的索引。

d 調試過程：

在編寫和測試程式碼時，我遇到了一些可能的問題，如邏輯錯誤或邊界情況。這些問題需要仔細調試，以確保算法的正確性和性能。通過逐步調試和打印輸出結果，我確認程式碼能夠正確地找到模式字串在文本中的匹配位置。

e 輸出結果：

以下是一些範例輸出結果：

當文本字串為"ABABDABACDABABCABAB"，模式字串為"ABABCABAB"時，KMP算法找到了模式字串在文本中的匹配位置：

在索引 10 處找到匹配串

當文本字串和模式字串由使用者輸入時，KMP算法會在使用者提供的文本中查找使用者提供的模式，並輸出匹配位置。

f 原始碼：

#include<bits/stdc++.h>
using namespace std;

// 計算匹配字串的最長前綴後綴匹配表（LPS陣列）
void computeLPSArray(const string& pattern, vector<int>& lps) {
    int length = 0;  // 前一個最長前綴後綴匹配的長度

    lps[0] = 0;  // lps[0] 總是為 0

    int i = 1;

    while (i < pattern.length()) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

// 使用KMP算法在文本中搜尋匹配字串
void KMPSearch(const string& text, const string& pattern) {
    int m = pattern.length();
    int n = text.length();

    vector<int> lps(m);
    computeLPSArray(pattern, lps);

    int i = 0;  // 用於文本[]
    int j = 0;  // 用於匹配串[]

    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }

        if (j == m) {
            // 找到匹配串，打印起始位置
            cout << "在索引 " << i - j << " 處找到匹配串" << endl;
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

// int main() {
//     string text = "ABABDABACDABABCABAB";
//     string pattern = "ABABCABAB";

//     KMPSearch(text, pattern);

//     return 0;
// }


int main() {
    string text;
    string pattern;
    cin>>text;
    cin>>pattern;

    KMPSearch(text, pattern);

    return 0;
}

發現新版本