3

クラスサブジェクトの場合、クラスが時系列で受け取る文字のセットでパターンを検索するクラスを実装する必要があります。クラスが受け取る各文字には、特定のソース（int IDで識別される惑星）があります。

データ構造を自分で実装する必要があるため、これらすべての文字を時系列で格納する文字列リストを実装しました。

問題は、同じ惑星（ソース）からの文字のパターンを一致させる必要があるため、各ソースでパターンの一致を行う必要があることです。

リスト全体を参照し、現在参照されているソースのみを考慮して、すべてのソースに対してこれを実行することで、Rabin Karpのような有名なパターンマッチングアルゴリズムを使用しようとしましたが、パフォーマンスは本当に劣っていて、ナイーブよりもさらに悪いです（ただし同期） 解決。

その場合、どのアルゴリズムがより効率的であるかについて何か考えがありますか？（単純な実装の場合のように、そのソースの実際の「検索状態」をどこかに保存することを意味する場合でも、参照している各文字を使用できるようにします）

PS：IDは有限（1から128）ですが、文字数は最大10⁷</p>になる可能性があります。

編集：うまくいけば物事を明確にするいくつかの詳細があります。

IntlFinder、私のクラスは、メソッドによって文字（または文字の配列）を受け取ることができますAdd(char* pszData, int nSource); したがって、各文字はソースIDと結合されます。ペア（文字、ソース）は、StringListにComList（追加の時系列で）格納されます。

パターンが私のクラスに存在するためには、同じソースに存在する必要があります。

例：

パターンSAYKOUKを探しているなら

（S、1）; （A、1）; （Y、1）; （K、1）; （Z、2）; （S、3）; （O、1）; （U、1）; （K、1）OK！

（S、1）; （A、1）; （Y、1）; （K、2）; （O、3）; （U、1）; （K、4）はOKではありません。

1つのソース（1から128の範囲）のみを考慮し、毎回リスト全体を参照すると、パターン検索方法が非常に遅くなるため、これは問題です。そして、これらのアルゴリズムのいずれかを使用して、さまざまなソースの文字を考慮に入れて、それらのいずれかで自分のパターンに出会ったときはいつでも知ることができません！

4

2 に答える 2

0

私は、古典的な「次へ」と「前へ」のポインタだけでなく、同じソースの文字を指す「次へ」と「前へ」のリンク付きリストを使用することになりました。このようにして、従来のパターン マッチング アルゴリズムを使用することができました。

于 2013-01-11T07:44:04.317 に答える
0

解決策は、ソースごとに個別の文字リストを保存し、これらのリストで個別にパターンを見つけることです。

于 2012-10-09T14:06:56.787 に答える