最小限の手順で部分文字列をすべて削除する

-1

部分文字列が指定された文字列に現れないようにするために必要な削除の最小回数を探したい。文字列と部分文字列の両方が小文字のみで構成されています。最小限の手順で部分文字列をすべて削除する

たとえば、文字列 "recorerecore"と部分文字列 "recore"の場合、2つの削除が必要です。文字列「recorecore」とサブ「ロコアナハ」について

私は第一および第三又は第二及び第四のいずれかで、2が必要となる文字列「recorecorecorecore」とサブ「ロコアナハ」の場合のみ1

を必要とします。

"rerecorecore"という文字列の場合、最初の文字を取り出すと再び2番目の文字列を取り出す必要があります。

私は、可能なすべての組み合わせで実際に削除し、最小値を見つけることを含むブルートフォース解決策を考えることができますが、これには時間がかかります。

これを行う方法は誰にも分かりますか？

2017-03-02 ffhm7

どの言語？ –

いずれも問題ありません。可能であればC++またはJava。 – ffhm7

再帰的にBoyer-Moore部分文字列を含む文字列を見つけたら削除

2017-03-02 03:29:11

最悪の場合でもそれはまだO（n^2）ですか？ – ffhm7

それはブルートフォースよりも速く...再帰のボーナスポイントよりも速いですが）しかし、それは "rerecorecore"に空の文字列を残します... –

それは私が考えていたものです。 2番目のオカレンスを削除して1つしか削除しないようにして、 "rerecore"を取得します。 – ffhm7

答えて