массив подстрок в массиве строк

Question

У меня есть два массива строк.Строки в одном массиве могут быть подмножеством строки в другом массиве.Мне нужно выяснить, какие все строки в одном массиве являются подстрока строк в другом массиве

Пример:

arr1 = ["firestorm", "peanut", "earthworm"]
arr2 = ["fire", "tree", "worm", "rest"]

Результат:

res = ["fire","worm", "rest"]

Мое решениеупоминается ниже.Но это занимает много времени.Я должен обработать тысячи слов.

Решение:

res =[]
arr1.each do |word1|
  arr2.each do |word2|
   if word1.include? word2
     res << word2
   end
  end
end

Пожалуйста, предложите мне более быстрый способ сделать это

Answer 1

К сожалению, мы не знаем ваше решение.

Но Array занимает больше места в памяти, чем String.Таким образом, вы можете преобразовать его.

arr1 = ["firestorm", "peanut", "earthworm"]
arr2 = ["fire", "tree", "worm", "rest"]

arr1 = arr1.join(',')

А затем

res = arr2.select { |word| arr1.include?(word) } #=> ["fire", "worm", "rest"]

или

res = arr2.select { |word| arr1.match?(word) } #=> ["fire", "worm", "rest"]

или

res = arr2.select { |word| arr1.match(word) } #=> ["fire", "worm", "rest"]

Answer 2

Из-за перекрывающихся терминов вам нужно сделать грубую силу, насколько я могу сказать:

def matched(find, list)
  list.flat_map { |e| find.flat_map { |f| e.scan(f) } }.uniq
end

На практике:

matched(%w[ fire tree worm rest ], %w[ firestorm peanut earthworm ])
# => ["fire", "rest", "worm"]

Где здесь %w используется какболее быстрый способ выражения списков.

Приближенное использование scan и flat_map:

def matched(find, list)
  rx = Regexp.union(find)

  list.flat_map { |e| e.scan(rx) }.uniq
end

При использовании Rexexp.union вы можете создать регулярное выражение, которое выполняется довольно быстро по сравнениюк отдельным тестам.

Где это не так точно:

matched(%w[ fire tree worm rest ], %w[ firestorm peanut earthworm ])
# => ["fire", "worm"]