複数の文字列

Question

にサブocurrenceを探す

1つの文字列の長さmおよびその他の文字列すべての長さと同じかmよりも大きいとRのセットのS言う考えます。サブシーケンスとしてSを持つ文字列を検索します。だから、

、Sはblrで、文字列のセットがある場合：

bangalore 
booleer 
bamboo 

それは最初の2つの文字列を返す必要があります。

Iは長さmのストリングSは、時間複雑度はO（n + m）の長さnの他のストリングTのsubsecuenceである場合、私は見つけることができることを承知しています。だから、私はちょうどセットの各要素についてこのアルゴリズムを行うことができますが、それはkのサイズであるO（k *（n + m））の時間の複雑さになります。同じ長さ）。これは、私が複数の文字列でこの問題を解決するのに役立つ何らかの前処理があるかどうか疑問に思います。

この問題を解決するために使用できる前処理または構造はありますか？ 私は達成するのに最適な時間の複雑さは何ですか？ この問題を解決する他の方法はありますか？ thatyou後

Answer 1

あなたはchはサブシーケンスとしてSを持つ集合である場合に検索する場合は、アルゴリズムが複雑にO（n）を持つことになりますけん引列CHとsの場合

public bool function(string ch, string s) 
     { 
      if (ch.Length < s.Length) 
       return false; 

      int j = 0; 
      for (int i = 0; i < ch.Length; i++) 
      { 
       if (ch[i] == s[j]) 
       { 
        j++; 
        if (s.Length == j) 
        { 
         return true; 
        } 
       } 
      } 
      return false; 
     } 

適用する必要がそれはあなたのすべての文字列のためにです

Answer 2

私はコードの実装がありませんでしたが、私は1983年の論文"Computing a longest common subsequence for a set of strings"をWJ HsuとMW Duが見つけました。

結論は、O（L）前処理時間（Lは集合内のすべての文字列の集合長さ）を実行することによって、O（P）の各検索を実行することが可能である針が干し草の中に現れる回数。