14

私は最近インタビューの質問に出くわしました: 最小サイズ 2 の特定の文字列で繰り返されるすべての部分文字列を見つけるには、アルゴリズムは効率的なものでなければなりません。

上記の質問のコードを以下に示しますが、効率的なものではありません。

#include <iostream>
#include <algorithm>
#include <iterator>
#include <set>
#include <string>

using namespace std;

int main()
{
    typedef string::const_iterator iterator;
    string s("ABCFABHYIFAB");
    set<string> found;

    if (2 < s.size())
        for (iterator i = s.begin() + 1, j = s.end(); i != j; ++i)
            for (iterator x = s.begin(); x != i; ++x)
            {
                iterator tmp = mismatch(i, j, x).second;;
                if (tmp - x > 1)
                    found.insert(string(x, tmp));
            }

            copy(found.begin(), found.end(),ostream_iterator<string>(cout, "\n"));
}

私の質問は、上記の質問を O(N) の時間複雑度で実装できるデータ構造はありますか?

あなたの答えがサフィックスツリーまたはハッシュである場合は、詳しく説明してください。

4

3 に答える 3

6

string の出力を分析すると、"AAAAAAAAAAAAAA"O(n²) 文字が含まれているため、アルゴリズムは少なくとも O(n²) です。

O(n²) を達成するには、s の各サフィックス (インデックス [1..n]、[2..n]、[3..n]、...、[n..n])のサフィックス ツリーを構築するだけです。 ）。文字列の 1 つに独自の終了ノードがなくても問題ありません。各ノードが使用される頻度を数えるだけです。

最後に、count>1 で各ノードを反復し、そのパスを出力します。

于 2012-04-07T14:36:53.953 に答える
2

これは単なる突飛なアイデアですが、試してみる価値はあります (ただし、O(N) メモリを消費します。ここで、N はプライマリ文字列の長さです)。アルゴリズムは O(N) ではありませんが、最適化できる可能性があります。

アイデアは、文字列の比較を頻繁に行いたくないということです。読み取ったデータのハッシュ (たとえば、読み取った文字の ASCII コードの合計) を収集し、ハッシュを比較できます。ハッシュが等しい場合、文字列は等しい可能性があります (後で確認する必要があります)。例えば：

ABCAB

A -> (65)
B -> (131, 66)
C -> (198, 133, 67)
A -> (263, 198, 132, 65)
B -> (329, 264, 198, 131, 66)

2 つ以上の長さの値にのみ関心があるため、最後の値を省略する必要があります (常に 1 文字に対応するため)。

131 と 198 の 2 つの等しい値が表示されます。131 は AB を表し、ペアを明らかにしますが、198 は ABC と BCA の両方を表し、手動チェックで拒否する必要があります。

それは単なるアイデアであり、ソリューション自体ではありません。ハッシュ関数は、部分文字列 (またはシーケンス構造) 内の文字の位置を説明するために拡張できます。ハッシュ値の格納方法は、パフォーマンスを向上させるために変更される場合があります (ただし、メモリ使用量が増加します)。

少しだけお役に立てば幸いです:)

于 2012-04-07T14:33:48.877 に答える
0

サフィックスツリーがすべての繰り返し部分文字列を取得する方法がわかりません。文字列「ミシシッピ」は、次のようにサフィックスツリーを構築します。

すみません、わかりました。「最後に、count>1 で各ノードを反復し、そのパスを出力します。」「count」は、この子ノードの数です

tree-->|---mississippi               m..mississippi
       |
       |---i-->|---ssi-->|---ssippi   i .. ississippi
       |       |         |
       |       |         |---ppi      issip,issipp,issippi
       |       |
       |       |---ppi                ip, ipp, ippi
       |
       |---s-->|---si-->|---ssippi    s .. ssissippi
       |       |        |
       |       |        |---ppi       ssip, ssipp, ssippi
       |       |
       |       |---i-->|---ssippi     si .. sissippi
       |               |
       |               |---ppi        sip, sipp, sippi
       |
       |---p-->|---pi                 p, pp, ppi
               |
               |---i                  p, pi

--- Suffix Tree for "mississippi" ---
于 2012-04-15T10:16:23.150 に答える