0

与えられたn文字列S1, S2, ..., SnとアルファベットセットA={a_1,a_2,....,a_m}。各文字列のアルファベットはすべて異なると想定します。次に、それぞれに転置インデックスを作成しますa_i (i=1,2...,m)。私の転置インデックスにも特別なものがあります。転置インデックスにa_iに1つの文字列が含まれている場合（たとえば）、のアルファベットはA順番に並んでいます。これ以上含める必要はありません。つまり、すべての文字列が転置リストに表示されるのは1回だけです。私の質問は、そのようなリストを迅速かつ効率的な方法で構築する方法ですか？複雑さには限界がありますか？S_2a_j (j=i+1,i+2,...,m)S_2

たとえば、A={a,b,e,g}, S1={abg}, S2={bg}, S3={gae}, S4={g}。次に、私の転置リストは次のようになります。

a: S1,S3
b: S2     (since S1 has appeared previously, so we don't need to include it here)
e: 
g: S4
4

1 に答える 1

3

私があなたの質問を正しく理解している場合、簡単な解決策は次のとおりです。

for each string in n strings
    find the "smallest" character in the string
    put the string in the list for the character

複雑さは文字列の全長に比例し、順序テストの定数を掛けます。

テストの簡単な方法がある場合（たとえば、文字がアルファベット順にあり、すべて小文字の場合は、<で十分です）、単にそれらを比較します。それ以外の場合は、ハッシュテーブルを使用することをお勧めします。ハッシュテーブルの各ペアは文字とその順序であり、後で単純に比較します。

于 2012-09-06T06:51:33.420 に答える