2

2 つの配列がある場合、たとえば、1 つの配列がもう 1 つの配列int[] one={1,2,4,6,54,3,34};ですint[] two={12,1,2,4,7,8,54,3,34,5}; 。例の「同じ部分」は[1,2,4]と[54,3,34]です。

PS擬似言語、c、c#、java、php、またはその他の言語を使用できます。

PS今、私は同じパーツを明確にします.同じパーツ要素にはリストがあります.

PSI は例を変更し、配列内の各項目の値は等しくありません (私の例を見ることができます)。

  1. 少なくとも 2 つの項目が一致する
  2. 2 つの配列内の一致項目のインデックスは一致する必要はありませんが、同じ部分は連続している必要があります。
4

3 に答える 3

1

2 つの配列 (「文字列」として表示) のサフィックス ツリーを作成し、2 つのツリーを比較できます。

特に、2 つのツリー (たとえば、小さい方の配列に関連付けられているツリー) の 1 つを選択し (A と呼びます)、そのトラバースを開始し、もう一方のツリーの移動を模倣します (B と呼びます)。

ツリー A のノード u にいて、このノードからツリー B の対応するノードに「移動」を複製できない場合は、「最大一致」(ルートから u までの綴り) を見つけたことになります。そして、u を根とする木 A の部分木を刈り込むことができます。

これは単なるアイデアです。それを基に構築する必要があります。O(n) で接尾辞ツリーを構築でき、この種の「双類似性」も O(n) であるため、最適に見えることに注意してください。

于 2011-04-30T17:05:09.443 に答える
0

いくつかの最適化を伴うほぼブルートフォース。最悪の場合O（n ^ 4）。nは短い配列のサイズです。

one=[1,2,4,6,54,3,34]
two=[12,2,4,3,54,3,5]
one_pos_list_map = {}  # map of value -> position list
one_pos_map = {}  # map of value -> map of position -> 1
for pos in xrange(len(one)):
  val = one[pos]
  if val not in one_pos_map:
    one_pos_map[val] = {}
  one_pos_map[val][pos] = 1 
  if val not in one_pos_list_map:
    one_pos_list_map[val] = []
  one_pos_list_map[val].append(pos)

checked = [False for i in xrange(len(two)*len(two))] 
def print_maximal_matches(start, end):
  idx = start * len(two) + end - 1 
  if (checked[idx] or end - start < 2): 
    return
  checked[idx] = True
  match_pos_list = one_pos_list_map.get(two[start], [])
  for match_pos in match_pos_list:
    found = True
    for i in xrange(start + 1, end): 
      if not one_pos_map.get(two[i], {}).get(match_pos + i - start, None):
        found = False
        break
    if found:
      print two[start:end]
      return

  print_maximal_matches(start + 1, end)
  print_maximal_matches(start, end - 1)

print_maximal_matches(0, len(two))
于 2011-04-30T17:59:02.553 に答える
0

これは、おそらく最も長い一般的なサブシーケンスの問題です。

于 2011-04-30T16:17:17.553 に答える