一个数组算法问题

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]。

PS你可以使用伪语言 ,c,c#,java,php或其他语言。

PS现在我也说清楚了 零件。相同的零件元素有 清单。

PSI 更改了示例，数组中每个项目的值不相等 （你可以看我的例子。）

1. 至少有两个项目
2. 与两个数组中匹配项目的索引匹配，不需要匹配 ，但相同部分必须是连续的。

Answer 1

您可以为两个数组（视为“字符串”）构建一个 后缀树 并比较两个数组树。

特别是，您可以选择两棵树中的一棵（例如与较小数组关联的一棵）（称为 A）并开始遍历它，模仿另一棵树上的移动（称为 B）。

如果您位于树 A 的节点 u 中，并且无法从该节点复制任何“移动”到树 B 的相应节点，那么您就找到了“最大匹配”（从 root 拼写到 u 的匹配）你可以修剪以u为根的树A的子树。

这只是一个想法，你必须以此为基础；请注意，您可以在 O(n) 中构建后缀树，并且这种“双相似性”也是 O(n)，所以它看起来是最优的。

Answer 2

这可能是最长公共子序列问题。

Answer 3

经过一些优化，几乎是蛮力。最坏情况 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))