1

テキスト内で目的のパターンが最初に出現する位置を見つけるために、C ++でHorspoolアルゴリズム（Anany Levitinによるアルゴリズムの設計と分析の概要、第2版、p。258に依存）を実装しました。ただし、アルゴリズムを拡張して、同じパターンの複数のオカレンスを検索したいと思います。残念ながら、私は後者の実装で立ち往生しました。あなたは私のコードを以下に見ることができます：

この関数は、テキスト内で最初に出現する目的のパターンの位置を計算して返します。シフトサイズはShiftTableに格納され、ShiftTableは目的のアルファベットの文字でインデックス付けされます。さらに、整数カウンターは、パターンとテキストの文字間の合計比較をカウントするために使用されます。カウンターの最初の値はゼロです。これを拡張して、同じパターンの複数のオカレンスを見つけるにはどうすればよいですか？

main（）関数の本体で次のことを試みましたが、機能しますが効率的ではありません。パターンの最初の出現に遭遇した場合、その位置が印刷され、パターンの最初の出現で終わるテキストの部分が消去されます。さらに、プログラムはパターンなどの残りのテキストをチェックします。

int counter=0;
while ((position = Find(pattern,text,ShiftTable,counter)) != -1) {
    cout << position << endl;
    text = text.erase(0,result+m);
}

何か案は？

4

1 に答える 1

2

現在、常に最初から開始します（i = m - 1）。前の検索を再開する場合は、開始する最後の位置を渡すだけです。

以下では、変数を削除しましたcounter–とにかく、その使用法は何ですか？

int Find(string pattern, string text, int *ShiftTable, int start = 0)

…そして…</p> 

i = start + m - 1,

…そして、次のようにコードを呼び出すだけです。

while ((position = Find(pattern,text,ShiftTable,position)) != -1)  {
    cout << position << endl;
    ++position;
}
于 2012-05-13T14:06:47.800 に答える