Как мне удалить самый длинный префикс, который появляется в массиве?

Question

У меня есть два массива, search и target. Я хочу найти самую длинную последовательность элементов search, которая начинается с начала search и которая также появляется в том же последовательном порядке в target. Затем я хочу вернуть копию target со всеми этими элементами.

Вот несколько примеров:

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.

Какой самый краткий способ выполнить эту проверку?

Answer 1

Решение от Nikita - хорошее решение, если вам нужно простое решение, которое выполняется в O (mn), где m и n - длины целевых и поисковых строк.немного сложная реализация, если вам это нужно.Ваша проблема очень похожа на общую проблему поиска строки.Наиболее эффективные алгоритмы поиска строк работают в обратном направлении, поэтому они способны находить суффиксы (если не точное совпадение).Поскольку вы хотите использовать префикс, вам необходимо сначала изменить поиск и целевые строки.Затем либо выполните поиск строки Boyer-Moore , либо KMP .Обычные реализации этих алгоритмов просто дадут вам точные совпадения.Но с небольшими изменениями вы можете вспомнить и самый длинный префиксный матч.Когда вы закончите, вы можете вернуться и удалить его в другой линейный проход.

Answer 2

Ну, это выглядит просто и достаточно компактно и не ставит под угрозу сложность

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

Массив # выберите документы

Улучшения приветствуются!
Кроме того, если ваш массив search может содержать значения nil, вам потребуется проверка границы здесь (s_index < search.length).

Answer 3

Вы можете использовать что-то вроде кода ниже.Но он определенно не настроен на производительность.

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

У меня нет времени, чтобы выработать полное решение, но я бы сказал, что есть два подхода:

1. Использовать пару внешних итераторов для запуска массивов впараллельно.В Интернете есть учебники по параллельной итерации или посмотрите копию языка программирования Ruby, который имеет хорошее описание

2. В качестве альтернативы вы можете зацикливаться на массиве поиска, отбрасывая элементыцелевой массив, пока либо целевой массив не станет пустым (в этом случае, где бы вы ни находились в поиске - это ваш префикс), или вы не доберетесь до конца поискового массива (в этом случае он целиком содержится в целевом массиве).

Есть хороший рецепт для параллельной итерации на http://flylib.com/books/en/2.44.1.124/1/