An array algorithm problem

Question

If I have two arrays.For example, One array is int[] one={1,2,4,6,54,3,34}; the other is int[] two={12,1,2,4,7,8,54,3,34,5}; The problem is how can I get "the same parts" between one and two. "The same parts" in the example are [1,2,4] and [54,3,34].

P.S.You can use pseudo language ,c,c#,java,php or other language.

P.S. Now I make clear the same parts.the same parts elements have the lists.

P.S.I have change the example,and value of each item in the array isn't equal (You can see my example.)

at least two items match
the index of the match item in the two arrays not necessary to match ,but the same parts must be continuous.

What programming language does this regard? Could you elaborate on "Get the same parts between"? — Hubro
– Hubro, Commented Apr 30, 2011 at 16:15
So you're looking for the groups of similar items in the same sequence in both arrays? What about single items on their own? Do the groups have to have the same indexes to match? — Mims H. Wright
– Mims H. Wright, Commented Apr 30, 2011 at 16:15
the same parts must at least match two items,but the groups don't have the same indexes to match — Alex
– Alex, Commented Apr 30, 2011 at 16:26
What about using the same entry twice? Consider the following examples: **** a=(1,2,3), b=(1,2,3,1,2) is the output ((1,2,3),(1,2)) or just ((1,2,3)) **** a=(1,2,3), b=(2,3,1,2) is the output ((1,2),(2,3)) or ??? — Tobber
– Tobber, Commented Apr 30, 2011 at 20:59

akappa · Accepted Answer · 2011-04-30 17:05:09Z

1

You can build a suffix tree for the two arrays (seen as 'strings') and compares the two trees.

In particular, you can choose one of the two trees (the one associated with the smaller array, say) (call it A) and start traversing it, mimicking the moves on the other tree (call it B).

If you are in a node u of tree A and you can't replicate any "move" from this node to the corresponding one of tree B, then you've found a "maximal match" (the one spelled from root to u) and you can prune the subtree of tree A rooted on u.

This is just an idea, you must build up on it; note that you can build a suffix tree in O(n) and this kind of "bisimilarity" is O(n) too, so it looks like optimal.

answered Apr 30, 2011 at 17:05

akappa

10.5k4 gold badges41 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

akappa Over a year ago

nice, I didn't know it is a well-known problem. The solution given, in principle, doesn't seem much different from mine (the node "u" in my solution is a "deepest internal node which has leaf nodes from all the strings in the subtree below it"). Of course the "wikipedia" solution is cleaner, so I'd implement it rather than performing "bisimulation" on the two trees.

Null Set · Accepted Answer · 2011-04-30 16:17:17Z

0

This is probably the longest common subsequence problem.

answered Apr 30, 2011 at 16:17

Null Set

5,4241 gold badge27 silver badges37 bronze badges

2 Comments

Alex Over a year ago

Sorry,it's not a lcs problem.But it inspired me.

akappa Over a year ago

He seeks for a "maximal common substrings", which is different (and far easier)

tarkeshwar · Accepted Answer · 2011-04-30 17:59:02Z

Nearly a brute force with some optimizations. Worst case O(n^4). n is size of shorter array.

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))

Collectives™ on Stack Overflow

An array algorithm problem

3 Answers 3

1 Comment

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related