9

次の問題を解決しようとしています。

任意の長さの文字列が与えられた場合、その文字列内で複数回出現し、重複のない最長の部分文字列を見つけます。

たとえば、入力文字列がABCABCABの場合、正しい出力は になりますABC。とは言えABCABません。これは、2 つの部分文字列が重複する場所で 2 回しか発生しないためです。これは許可されていません。

数千文字を含む文字列について、これを合理的に迅速に解決する方法はありますか?

(そして、誰かが尋ねる前に、これは宿題ではありません。リンデンマイヤー フラクタルのレンダリングを最適化する方法を検討しています。単純なタートル グラフィックス システムを使用して高い反復レベルで描画するには、過度の時間がかかる傾向があるためです。)

4

4 に答える 4

0

このタイプの分析は、ゲノム配列でよく行われます。この紙を見てください。繰り返しを解決するための効率的な実装（c ++）があります：http://www.complex-systems.com/pdf/17-4-4.pdf はあなたが探しているものかもしれません

于 2013-05-21T15:00:33.357 に答える
0

まず、部分文字列の開始記号を定義し、長さを定義する必要があります。可能なすべての開始位置を反復し、長さのバイナリ検索を実行して長さを計算します (長さ a の substr を見つけることができれば、より長い長さで見つけることができます。関数は単調に見えるので、ビン検索で問題ありません)。次に、等しい部分文字列が N であることを見つけます。KMP または Rabin-Karp を使用して、任意の線形アルゴリズムで問題ありません。合計 N*N*log(N)。複雑すぎませんか？コードは次のようなものです。

for(int i=0;i<input.length();++i)
    {
        int l = i;
        int r = input.length();
        while(l <= r)
        {
            int middle = l + ((r - l) >> 1);
            Check if string [i;middle] can be found in initial string. Should be done in O(n); You need to check parts of initial string [0,i-1], [middle+1;length()-1];
            if (found)
                l = middle + 1;
            else
                r = middle - 1;
        }
    }

わかる？

于 2012-08-07T20:39:56.677 に答える