配列の範囲を見つける

Question

私は、仕事で思い浮かぶ次の問題（最適な解決策）を見つけようとしていました。結局、十分な解決策が得られるように解決しましたが、 1。

... _nを文字列の配列とします。

レッツS ... _Kは、配列のそれらのすべてはまたのメンバー、文字列の順序なしリストでありますね。

aにあるsのインデックス範囲の最小セットを見つけることです。

たとえば、a = ["x"、 "y"、 "a"、 "f"、 "c"]およびs = {"c"、 "y"、 "f"}の場合、配列がゼロからインデックスされていると仮定して、（1; 1）、（3; 4）となります。

aは、通常、かなり小さく（数十万要素）、sは比較的小さく、通常は長さが<ログ（長さ（a））です。

問題は次のとおりです。この問題の時間効率的なアルゴリズムを見つけることができますか？

ちょっと速いが重要な更新：この操作は異なるsの値で実行する必要がありますが、同じaがたくさんあります。したがって、aに基づいた事前計算は許可されていますが、それは唯一の方法です。

Answer 1

要素からインデックスにマッピングするハッシュテーブルH(a)をビルドします。a _X->xO(n)時間と空間に。次に、それぞれ _yを検索してH(a)（O(1)の平均で、sの合計でO(k)）の時間を追跡し、範囲を把握します。そのためには、pair(min_index, max_index)の配列をmin_indexでソートして、範囲を探すか、新しい1要素の範囲を挿入するかをバイナリ検索で行うことができます。
全体的には、上記の解決策には、O(n + k + k * log(nb_ranges))時間とO(n + nb_ranges)時間がかかります。

Answer 2

Sの要素を、O（1）の近くにあるメンバーまたはハッシュテーブルに入れてメンバーシップをチェックすることができます。次に、Sの要素を現在カバーしているかどうかを判断するためのフラグと、そのカバーの開始位置を指定して、Aに対して線形スキャンを実行します。 O（n + k）でなければなりません。

Answer 3

これはPythonで書かれ、あなたが望むものである：

def flattened(indexes): 
    s, rest = indexes[0], indexes[1:] 
    result = (s, s) 
    for e in rest: 
     if e == result[1] + 1: 
      result = (result[0], e) 
     else: 
      yield result 
      result = (e, e) 
    yield result 

a = ["x", "y", "a", "f", "c"] 
s = ["c", "y", "f"] 

# Create lookup table of ai to index in a 
src_indexes = dict((key, i) for i, key in enumerate(a)) 

# Create sorted list of all indexes into a 
raw_dst_indexes = sorted(src_indexes[key] for key in s) 

# Convert sorted list of indexes into an array of ranges 
dst_indexes = [r for r in flattened(raw_dst_indexes)] 

print dst_indexes