こういう事したい人はあまりいないようで（探して見つからなかった）、しょうがなく自分で考えて書いてみたら随分長くなってしまったので晒してみます。特に意識したわけではありませんが、ヒューリスティック探索系のアルゴリズムになったかと思います。
コードと解説
class String
def carving(reference_string)
rf = reference_string.split("")
rate = ->(a) {
r1 = (a & rf).size / a.size.to_f
r2 = [ a.size, rf.size ].min / (( a.size + rf.size ).to_f / 2)
2 / ( 1/r1 + 1/r2 )
}
p_length = [ (rf.size * 2.0).round, length ].min
p_string = split("")
prev_d = []
prev_rate = 0.0
loop do
return "" if p_length.zero?
this_d = p_string.each_cons(p_length).max_by {|a| rate[a]}
this_rate = rate[this_d]
return prev_d.join if prev_rate >= this_rate
prev_d = this_d
prev_rate = this_rate
p_string = this_d
p_length -= 1
end
end
end
s = <<STR
ああ、待っているだろう。ありがとう、セリヌンティウス。
よくも私を信じてくれた。それを思えば、たまらない。
友と友の間の信実は、この世で一ばん誇るべき宝なのだからな。
STR
puts s.carving("セぃリィオス")
# => "セリヌンティウス"
# 参照文字列は、元の文字列と微妙に異なる（ノイズを含む）ものとなっています
基本的なアイデアとしては、参照文字列の2倍程度の長さからはじめて、部分文字列と参照文字列の類似度を評価していき、最大になる部分文字列(とう、セリヌンティウス)を得ます。
そうしたなら、さらにその部分文字列により類似度の高いものが含まれていないか？という探索をします（とう、セリヌンティウス→う、セリヌンティウス→、セリヌンティウス→セリヌンティウス[極大rate]→セリヌンティウ）。類似度の極大値をもってreturnとします。
計算量はselfの長さNに対してO(N)です。
最初は類似度の定義をレーベンシュタイン距離にしようと思ったのですが、計算コストの高さが気になったので、独自に考えることにしました。
類似度の定義は、「共通文字の含有度」「文字長さの近さ」の調和平均です（とくに学術的な裏付けはありませんがイイ感じです）。
実行速度
def bench(n=1000, &proc)
require 'benchmark'
res = Benchmark.realtime{ n.times(&proc) }
puts ( res / n )
end
bench{
s.carving("セぃリィオス")
}
# 0.000493478
このケースでは、1実行あたり約0.5msでできています
（Intel Core i5-4288U @ 2.60GHzにて）
追記
探索問題としてとらえたとき、線形時間になるほど激しく枝刈りしており懸念してたことですが、どうもやっぱり局所解に落ちてしまうことがあるようで。
s = <<STR
ウィスキー飲めないって人は、騙されたと思ってポケットサイズの瓶を冷凍庫に入れてみてくれ。
瓶が真っ白になったら、グラスにちょこっとだけ入れて舐めてみろ。そしてビターチョコをかじるんだ。
世界が変わるぞ。ウィスキーは鍵なんだ。そっと心の扉を開けてくれる。悩みなんか吹き飛ぶよ。
https://twitter.com/harupaca/status/138909943347675136
STR
puts s.carving("ウイスキい")
# "ウィスキー飲めない"
類似度の工夫（2gram使ったり）だけではうまくいかなかったので、より精度を向上させるには、最適解に到れる枝を刈ってしまわないようにする工夫が避けられないようです。