Проблема алгоритма массива

Question

Если у меня есть два массива. Например, Один массив 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].

P.S. Вы можете использовать псевдо язык , c, c #, java, php или другой язык.

P.S. Теперь я проясняю то же самое Parts.The элементы частей имеют списки.

P.S. У меня есть пример, и значение каждого элемента в массиве не равно (Вы можете увидеть мой пример.)

1. как минимум два элемента соответствуют
2. индекс элемента сопоставления в двух массивах, для которого не нужно сопоставлять , но одни и те же части должны быть непрерывными.

Answer 1

Вы можете построить дерево суффиксов для двух массивов (видимых как 'строки') и сравнить два дерева.

В частности, вы можете выбрать одно из двух деревьев (скажем, связанный с меньшим массивом (назовите его A) и начните обходить его, имитируя ходы другого дерева (назовите его B).

Если вы находитесь в узле u дерева A иВы не можете повторить любое «перемещение» из этого узла в соответствующее дерево B, затем вы нашли «максимальное совпадение» (записанное от корня до u), и вы можете обрезать поддерево дерева A с корнем наu.

Это всего лишь идея, вы должны опираться на нее;обратите внимание, что вы можете построить дерево суффиксов в O (n), и этот тип "двойственности" также равен O (n), поэтому он выглядит оптимальным.

Answer 2

Почти грубая сила с некоторыми оптимизациями. Худший случай 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))

Answer 3

Это, вероятно, самая длинная общая подпоследовательность проблема .