Удалить дубликаты подстрок из двух строк

Question

Я пишу скрипт для удаления самых длинных дублирующих подстрок из двух строк.Есть две строки: a и b:

a = "Hello World: This is a test message"
b = "Good Bye: This is a test message"

Поскольку есть дубликаты: : This is a test message, они удаляются из обеих строк.Я пытаюсь получить результат ниже:

"Hello World"
"Good Bye"

Другой пример:

a = "Zoo is awesome. Hello World: This is not a test message"
b = "Zoo is not awesome. Good Bye: This is a test message"

с ожидаемым результатом:

"Zoo is awesome. Hello World: This is not"
"Zoo is not awesome. Good Bye: This is"

Я думал разделитьстроки в массивы подстрок и вычтите два массива, чтобы получить уникальную подстроку.Пожалуйста, сообщите, если есть лучший способ сделать это.

Answer 1

Рассматривая удаление только подстроки, совпадающей с трейлом, используя массивы, я пришел к следующему решению:

a = "Hello World: This is a test message"
b = "Good Bye: This is a test message"
# a = "Zoo is awesome. Hello World: This is not a test message"
# b = "Zoo is not awesome. Good Bye: This is a test message"

a_ary = a.split(/\b/)
b_ary = b.split(/\b/)

zipped = a_ary.reverse.zip(b_ary.reverse)
dropped = zipped.drop_while { |(a,b)| a == b }

dropped.reverse.transpose.map{|w| w.join('')}
#=> ["Hello World", "Good Bye"]
#=> ["Zoo is awesome. Hello World: This is not", "Zoo is not awesome. Good Bye: This is"]

Один вкладыш:

a.split(/\b/).reverse.zip(b.split(/\b/).reverse).drop_while { |(a,b)| a == b }.reverse.transpose.map{|w| w.join('')}

Answer 2

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

def remove_common_ending(str1, str2)
  return ["", ""] if str1 == str2
  n = [str1.size, str2.size].min
  return [str1, str2] if n.zero?
  i = (1..n).find { |i| str1[-i].downcase != str2[-i].downcase }
  [str1[0..-i], str2[0..-i]]
end

remove_common_ending(str1, str2)
  #=> ["Hello World", "Good Bye"] 

Другая возможная интерпретация заключается в том, что самую длинную общую подстроку необходимо удалить из обеих строк.Далее следует один из способов сделать это.Мой подход аналогичен @ tadman, за исключением того, что я начинаю с длины максимально длинной общей подстроки, затем постепенно сокращаю эту длину до тех пор, пока не будет найдена подстрока, которая появляется в обеих строках.Таким образом, нет необходимости искать более короткие подходящие подстроки.

def longest_common_substring(str1, str2)
  return '' if str1.empty? || str2.empty?
  s1, s2 = str1.downcase, str2.downcase
  (s1, s2 = s2, s1) if s2.size < s1.size
  sz1 = s1.size
  sz1.downto(1) do |len|
    puts "Checking #{sz1-len+1} substrings of length #{len}..."
    (0..sz1-len).each do |i|
      s = s1[i, len]
      return s if s2.include?(s)
    end
  end 
end    

Я добавил оператор puts, чтобы показать, какие вычисления выполняются.Обратите внимание, что я ищу в более длинной строке (str1) подстроки более короткой строки (str2).

str1 = "Hello World: This is a test message"
str2 = "Good Bye: This is a test message"  

s = longest_common_substring(str1, str2)    
Checking 1 substrings of length 32...
Checking 2 substrings of length 31...
Checking 3 substrings of length 30...
Checking 4 substrings of length 29...
Checking 5 substrings of length 28...
Checking 6 substrings of length 27...
Checking 7 substrings of length 26...
Checking 8 substrings of length 25...
Checking 9 substrings of length 24...
  #=> ": This is a test message"

r = /#{Regexp.escape(s)}/i
  #=> /:\ this\ is\ a\ test\ message/i
str1.sub(r,'') #=> "Hello World"
str2.sub(r,'') #=> "Good Bye"

Как видно, количество подстрок более короткой строки (str2), котороебыли проверены до того, как была найдена самая длинная общая подстрока (1+10)*10/2-1 #=> 54.

Answer 3

У Google есть замечательная библиотека под названием diff_match_patch, которая делает символьные различия двух строк сверхбыстрым способом, и - для Ruby есть драгоценный камень!

require 'diff_match_patch'
longest = DiffMatchPatch.new.diff_main(a, b).    # find diffs
    select { |type, text| type == :equal }.      # select only equal pieces
    map(&:last).                                 # get just text
    max_by(&:length)                             # find the longest one
a[longest] = ''                                  # delete this piece from a
b[longest] = ''                                  #               and from b

puts a
# => Hello world
puts b
# => Good bye

Answer 4

Сначала вы должны найти самую длинную общую подстроку, а затем вычесть ее.Чтобы найти самую длинную общую подстроку, вам нужно знать все подстроки:

def substrings(string)
  (0..string.length-1).flat_map do |i|
    (1..string.length-i).flat_map do |j|
      string[i,j]
    end
  end
end

Это делается, начиная с индекса 0 и беря подстроку полной длины, затем подстроку длины-1 и т. Д. Перед перемещениеминдексировать 1 и повторять итеративно.

Это возвращает их в довольно произвольном порядке, хотя сортировать по длине тривиально.Следующий шаг - посмотреть, какое из этих совпадений all? заданных элементов:

def lcs(*list)
  list = list.sort_by(&:length)
  subs = substrings(list.first).sort_by(&:length).reverse

  subs.find do |str|
    list.all? do |entry|
      entry.include?(str)
    end
  end
end

Здесь выбирается самая короткая запись (порядок сортировки first), поскольку она обязательно будет содержать самую длинную общую строку.

Это дает вам подстроку, которую вы хотите удалить, так что вы можете применить это:

def uniqueify(*list)
  list_lcs = lcs(*list)

  list.map do |entry|
    entry.sub(list_lcs, '')
  end
end

, который затем работает:

a = "Hello World: This is a test message"
b = "Good Bye: This is a test message"

lcs(a,b)
# => ": This is a test message"

uniqueify(a,b)
# => ["Hello World", "Good Bye"]