重なる文字を含めた連結 Ruby

Question

文字列の連結で例えば画像のような、apple letter git という文字が入力されたときに、
apple と　letter はそれぞれ末尾文字、頭文字が重なっていて、letter と　git は何も重なってないので
結果　applettergit と出力する、みたいなことをやりたいのですが、文字列の連結以外やり方がわからないので、
教えていただきたいです。

↓出力

applettergit

Answer 1

最近同様の質問に回答しました。
https://teratail.com/questions/148136

words = %w/apple letter git/

puts words.join("\n").gsub(/(.*)\n(?=\1)/,"")

Answer 2

何かアルゴリズムがありそうな気がしますが、単純に一致している部分を最長の場合から探す以外に方法が思いつきませんでした。

str_list = %w|apple letter git|

def overlap_join(a, b)
  b.length.downto(0) do |n|
    break a + b[n, b.length - n] if a.end_with?(b[0, n])
  end
end

puts str_list.inject("", &method(:overlap_join))