IList <T> String.IndexOfのバージョン（単一のオブジェクトだけでなくサブストリングを見つける）

Question

List<T>.IndexOf(List<T>)の実装を探しています。私はList<<T>.IndexOf(T)しか.NETクラスライブラリに見つかりませんでした。

私はList longListとList possibleSubListを持っています。私はpossibleSubListがlongListの中にサブストリングとして見つかるかどうか知りたいのですが、その場合はインデックスをlongListにします。

これは基本的にSystem.String.IndexOfと同じセマンティクスです。誰がこれを何と呼ぶべきか、それとも良い実装があるのか​​を知っていますか？

擬似コード例：
{1, 2, 3, 9, 8, 7}.IndexOf({3, 9, 8}) = 2
{1, 2, 3, 9, 8, 7}.IndexOf({1, 2, 3, 9, 8, 7}) = 0
{1, 2, 3, 9, 8, 7}.IndexOf({2, 9}) = -1 (not found)


明確化：私はすでにこのの直接の実装（ループのための2つのネストされた）を持っていますが、私のリストはかなり長く、これはパフォーマンスの影響を受けやすい地域です。私は〜O（m * n）よりも効率的な実装を見つけることを望んでいます。私は単語「サブ文字列」の使用は少し誤解を招くようだったと思います（擬似コード）

findsubstring(list<T> s, list<T> m){ 
    for(int i=0; i<s.length;++i) 
     for(int j=0; j<m.length;++j) 
      if(s[i] != s[j]) 
       break; 
      if(j==m.length-1) 
       return i; 
    return -1; 
} 

Answer 1

リニアZ-インデックスおそらく、O（n）の複雑さ（小さなアルファベットでは、O（n）から期待されるよりもはるかに優れた性能を発揮するパターンが同じで、コーパスが動的である今日の最速のサブリスト検索アルゴリズムの1つです。 ZIndexingはインデックスをスキップする機会が豊富です）：

セントラルフロリダ大学のShaojie Zhangの指導のもと、私は遺伝学アルゴリズムクラスに実装しました。私はC＃にアルゴリズムを適用しました。具体的には汎用のIList<T>を使用します。使用する場合は、クレジットを与えてください。これらの技術の研究はhereで利用できます。具体的には講義ノートhereをご覧ください。いずれにしても

は、私は文字列で、この場合には（検索を実行する方法の例についてはTestZIndexing.csの内部で利用可能なコードhere

がルックを作ったが、あなたはできるはずであるジェネリックを使用してきました等価演算子で何かを使う）。

使い方は簡単です：

IEnumerable<int> LinearZIndexer.FindZ<T>(
     IList<T> patternSequence, IList<T> sourceSequence, bool bMatchFirstOnly) 
     where T: IComparable; 

そして、いくつかのDNAが円形であるとして、私は、円形の変種があります

IEnumerable<int> LinearZIndexer.FindZCircular<T>(
     IList<T> patternSequence, IList<T> sourceSequence, bool bMatchFirstOnly) 
     where T: IComparable; 

をのがさらに高速にそれをやってみましょう：接尾辞木

また、O（n）よりも優れたパフォーマンスを得たい場合は、O（m）を得ることができます（mはパターンリストのサイズです）。サフィックスTre e。これは、パターンが変化し、コーパスが同じままである場合（前のケースの反対）に機能します。私がTestSuffixTree.csのために寄稿した同じ図書館を見てください。ここでの唯一の違いは、事前にサフィックスツリーを構築する必要があるため、大きなコーパスに対して複数のパターン検索を行うことですが、そのサフィックスツリーを構築するためのO（n）アルゴリズムとSpace（n）アルゴリズムを提供します。

呼び出しも同様に簡単であり、そして再び、IComparableをを提供して何かを使用することができます。

string strTest = "bananabananaorangebananaorangebananabananabananaban"; 
string[] strFind = {"banana", "orange", "ban"}; 

// I use char, but you can use any class or primitive that 
// supports IComparable 

var tree = new SuffixTree<char>(); 
tree.BuildTree(strTest.ToCharArray()); 
var results = tree.Find(str.ToCharArray()); 
foreach(var r in results) Console.WriteLine(r); 

をお楽しみください。

Answer 2

は、文字列検索アルゴリズムを使用してください。大きなリストに、別のリストの要素のシーケンス全体に一致する要素のサブシーケンスが含まれているかどうかを確認しようとしていると思います。私はあなたが正しく欲しいものを理解していればこれが、あなたはそれが何をしたいのか行う必要があります拡張メソッドです：

public static int IndexOfSequence<T>(this IEnumerable<T> longL, IEnumerable<T> subL) 
    { 
     var longList = longL.ToList(); 
     var subList = subL.ToList(); 

     int longCount = longList.Count; 
     int subCount = subList.Count; 

     if (subCount > longCount) 
     { 
      return -1; 
     } 

     int numTries = longCount - subCount + 1; 

     for (int i = 0; i < numTries; i++) 
     { 
      var newList = new List<T>(longList.Skip(i).Take(subCount)); 

      if (newList.SequenceEqual(subList)) 
      { 
       return i; 
      } 
     } 

     return -1; 
    } 

次に、あなたが好き、それを使用することができます。

int index = longList.IndexOfSequence(possibleSubList); 

Answer 3

：