How do I remove the longest prefix that appears in an array?

Question

I have two arrays, search and target. I want to find the longest sequence of elements of search that starts from the beginning of search and which also appears in the same consecutive order in target. Then I want to return a copy of target with those elements removed.

Here are some examples:

search = [4, "apple", 6, "turnip"]
target = [5, "apple", 4, "orange"]
=> [5, "apple", "orange"]           # Delete [4], the longest matching
                                    # prefix of `search`.

search = [4, "apple", 6, "turnip"]
target = [5, "apple", 4, "apple"]
=> [5, "apple"]                     # Delete [4, "apple"], the longest matching
                                    # prefix of `search`.

search = [4, "apple", 6, "turnip"]
target = [5, "apple", 6, 7]
=> [5, "apple", 6, 7]               # Nothing was matched; don't delete anything.

What's the most concise way to perform this check?

Answer 1

I don't have time to work out a full solution, but I'd say there are two approaches:

1. Use a pair of external iterators to run over the arrays in parallel. There are tutorials on parallel iteration around on the internet, or check out a copy of The Ruby Programming Language which has a good description

2. Alternatively you could loop over the search array, popping items off the target array, until either the target array is empty (in which case whereever you got to in the search is your prefix), or you get to the end of the search array (in which case it is entirely contained in the target array).

There's a nice recipe for parallel iteration at http://flylib.com/books/en/2.44.1.124/1/

Answer 2

Well, this looks simple and compact enough and doesn't compromise complexity

s_index = 0
result = target.select do |t|
  match = search[s_index] == t
  s_index += 1 if match
  !match
end

Array#select docs

Improvements are welcome!
Also, if your search array can contain nil values, you'll need a border check here (s_index < search.length).

Answer 3

You can use something like the code below. But it definitely not tuned for performance.

class Array
  def remove(start, length)
    length.times {delete_at start}
    self
  end
end

def remove(a,b)
  b.length.downto(1) do |len|
    index = a.each_cons(len).to_a.index b[0,len]
    return a.remove(index, len) if index
  end
  return a
end

search = [4, "apple", 6, "turnip"]
target = [5, "apple", 4, "orange"]
remove target, search

Answer 4

The solution by Nikita is a good one if you want simple solution that runs in O(m.n) where m and n are lengths of target and search strings.

You can do this in linear time with a bit complex implementation if you need it. Your problem is very much like a general string search problem. Most efficient string search algorithms work backwards so they are good at finding suffixes (if not exact match). Since you want prefix, you would need to first reverse your search and target strings. Then either run Boyer-Moore or KMP string search. Usual implementations of these algorithms would just give you exact matches. But with slight modification, you can remember the longest prefix match as well. When you are done, you can go back and delete it in another linear pass.