データ構造実機実験レポート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;
}

新しいバージョンが見つかりました