今、問題に直面しています.NxNの中に特定のMxM行列が現れる時間を数える必要があります（これは最初の行列よりも大きくなければなりません）。 ）。これを行う方法に関するヒント？私はC言語で実装しようとしており、それを変更するオプションはありません。大きい方の内部の行列の出現数をカウントするアルゴリズム
リビジョン1
こんにちは皆、私は本当に問題に関するすべての答えや意見に感謝を言いたいと思います。私は、何時間もの努力の結果、Boyer-Mooreのアプローチに厳密に似ているわけではなく、むしろ私自身のアルゴリズムのようなソリューションになっています。私はそれが一度テストされ、完了したことを出版する予定です。このソリューションは現在、CライブラリMPIを使用して大学のクラスタを使用してスピードの最適化を行うためにパラレル化されています。
Hmは、文字列一致の2次元バージョンのように聞こえる。 Boyer-Mooreの2D版があるのだろうか？
A Boyer-Moore Approach for Two-Dimensional Matching
ああ、明らかにそこにあります。 :-)
すぐに頭に浮かんだ一つのアプローチ：
N * N「文字」の線形文字列と長さの線形正規表現のような小さな行列（M + 1）として、大きな行列を扱います各行の最初のM個の位置に "リテラル文字"を含む* Mと、各行の残りの位置にある.{N-M}に相当する。正規表現をDFAにコンパイルして実行します。
すべての一致が見つかるまでの時間はO（N * N）です。私は、（愛好家の1-d部分文字列検索アルゴリズムの適応）は動作するだろうが、これはあまりにも悪くはありませんが見事なアルゴリズムがあると思う。
最近、2Dサフィックスツリーを構築するための高速アルゴリズムが開発されています。これらは、より大きな行列のサイズに依存しない時間に大きな行列のいずれかの正方形の部分行列を見つけるために使用することができます。
あなたが見に加入する必要がありますそれらの論文。
私は2Dの接尾辞木を構築し、検索することを期待：
私も線形時間を期待されている無作為化構築アルゴリズムを説明し、この自由に利用できるものを発見しました1つの行列で多くの異なる部分行列を検索する必要がある場合は速くなりますが、毎回異なる行列を検索する場合はおそらく2D Boyer-Mooreよりも遅いでしょう。
"より大きい行列のサイズに依存しない"は間違いなく間違いです。 NxN行列で1x1の部分行列を探すことを検討してください。 N^2時間未満でそれを見つける方法はありません。おそらく、あなたは小さな行列の大きさから独立していたのです...？ –
@R：インデックス作成時間を忘れてしまいます。もちろん、NxNのすべての要素を調べる必要があります。それが構築されると、2次元サフィックスツリーはNxNマトリックスの1x1サブマトリックスをほぼ1ステップで検索できるようになります.1Dサフィックスツリーはシェイクスピアのすべての作品でおよそ6ステップで "バナナ" 。 （これは、単一のオカレンスを見つけるための時間の複雑さです。すべてのオカレンスをリストするには、より多くの時間が必要です）。 –
あなたはこれまで考えていたことはありますか？ –
@Oli_Charlesworth私は線形行列表現について考えていましたが、Cでそれらを実装し、ベクトルパターンマッチングアルゴリズムを探していましたが、少なくとも1つから始めるにはいくつかのポインタが必要だったことを念頭に置いています。 – guiman