14

文字列内で重複しない最長の繰り返し部分文字列を見つける必要があります。使用可能な文字列のサフィックス ツリーとサフィックス配列があります。

オーバーラップが許可されている場合、答えは自明です (サフィックス ツリーで最も深い親ノード)。

たとえば、String = "acaca" の場合

重複を許容する場合は「aca」、重複を許容しない場合は「ac」または「ca」となります。

アルゴリズムまたは高レベルのアイデアのみが必要です。

PS: 試してみましたが、ウェブ上で見つけられる明確な答えはありません。

4

8 に答える 8

2

サフィックス ツリーを構築することにより、プレフィックス P を共有するすべてのサフィックスは、ツリー内の共通の祖先の子孫になります。そのサブツリーのサフィックスの最大インデックスと最小インデックスを格納することにより、長さ min(depth, max-min) の繰り返される重複しない部分文字列を保証できます。ここで、max-min はそれらの間の距離であり、depth は長さです。それらの共通の接頭辞。望ましい値は、そのような値が最大のノードです。

于 2015-09-25T12:31:38.777 に答える
2

接尾辞ツリーを使用して重複しない最長の繰り返し部分文字列を取得するための実用的なアルゴリズムの明確な説明を見つけるのに苦労したので、さまざまな情報源から収集したバージョンを共有したいと思います。

アルゴリズム

  1. 入力文字列Sのサフィックス ツリーを構築します( Sにはない特殊文字で終了します)。各リーフ ノードは、S のサフィックス Si に対応し、S内のSiの対応する開始位置 i が割り当てられます。
  2. ツリー内の各ノードに、そのサブツリーでの最小および最大サフィックス インデックスを示す ペア(i min、i max )を割り当てます。
    1. 各葉についてi min = i max = i .
    2. 各内部ノードのi minは最小値で、i maxはすべての子孫ノードのインデックスの最大インデックスです。
  3. すべての内部ノードvについて、ルートからvへのパス上のすべてのエッジ ラベル (接頭辞) を連結して得られる文字列をP vとする。vでの対応するi minおよびi maxについて、 i min + length( P v ) ≤ i maxを満たすすべてのP vを収集します。
  4. これらのP vの中で最も長いものは、少なくとも 2 回発生するSの重複しない部分文字列の中で最も長いものです。

説明

Sの部分文字列がSで少なくとも 2 回出現する場合、それは2 つの接尾辞S iとS jの共通の接頭辞Pです。ここで、iとjはSでのそれぞれの開始位置を示します。したがって、 Sのサフィックス ツリーには、ルートからvへのパスのすべてのエッジ ラベルの連結がPに等しくなるように、 iとjに対応する 2 つの子孫リーフを持つ内部ノードvが存在します。

最も深いそのようなノードv (対応するプレフィックスの長さに関して) は、Sで重複する可能性のある最長の部分文字列をマークします。重複する部分文字列が考慮されないようにするために、Pがiとjの間の距離よりも長くないことを確認する必要があります。

したがって、各ノードの最小および最大インデックスi minおよびi maxを計算します。これらは、共通のプレフィックスを共有するSの左端および右端のサフィックスの位置に対応します。ノードの最小インデックスと最大インデックスは、その子孫の値から簡単に取得できます。(少なくともk回発生する最長の部分文字列を探す場合、インデックスの計算はより複雑になります。これは、最も離れた 2 つのインデックスだけでなく、すべての子孫のインデックスの距離を考慮する必要があるためです。) i min + length( P ) ≤ iを満たすプレフィックスP最大で、 S iで始まるPがサフィックスS jと重ならないように十分に短いことを確認します。

その他の注意事項

  • 長さnの文字列のサフィックス ツリーは、Θ( n ) 時間と空間で構築できます。このアルゴリズムの変更により、全体の実行時間が依然として Θ( n )内にあるような漸近動作が悪化することはありません。
  • このアルゴリズムは、考えられるすべての解を見つけるわけではありません。重複しない最長の部分文字列が複数ある場合は、最大の位置から始まる部分文字列のみが検出されます。
  • アルゴリズムを変更して、重複しない最長部分文字列の繰り返し回数もカウントするか、少なくともk回の繰り返しで解のみを見つけることができるはずです。このためには、最小および最大の inidice だけでなく、ノードのすべてのサブツリーのインデックスも考慮する必要があります。上記の範囲条件は、隣接するインデックスのペアごとに保持する必要があります。
于 2019-08-25T21:57:02.230 に答える
1

最も簡単な解決策は、ブルートフォース攻撃のようなものです。重複が許可されている最長の文字列を見つけて使用し、その回答に重複があるかどうかを確認するアルゴリズムがあります。重複している場合は、2番目に長い文字列を見つけて、重複があるかどうかを確認します。これにより、既存の検索アルゴリズムになり、次に正規表現カウント操作になります。

于 2012-09-30T04:06:33.143 に答える
0

完全なコード:

#include <bits/stdc++.h>
using namespace std;
int cplen(string a,string b){
    int i,to=min(a.length(),b.length());
    int ret=0;
    for(i=0;i<to;i++){
        if(a[i]==b[i])ret++;
        else {
            return ret;}
        }
    return ret;
    }
int main(){
    {
        int len,i;
        string str;
        cin>>str;
        len=str.length();
        vector<pair<string,int> >vv;
        map<char,int>hatbc;
        string pp="";
        for(i=len-1;i>=0;i--){
            hatbc[str[i]]++;
            pp=str.substr(i,len-i);
            vv.push_back(make_pair(pp,i));
            }
        if(len==1 || (int)hatbc.size()==len){
            printf("0\n");
            continue;
            }
        if(hatbc.size()==1){
            printf("%d\n",len/2);
            continue;
            }
        char prev=str[0];
        int foo=1,koo=0;
        for(i=1;i<len;){
            while(str[i]==prev && i<len){i++;foo++;}
            prev=str[i];
            i+=1;
            if(koo<foo)koo=foo;
            foo=1;
            }

        sort(vv.begin(),vv.end());
        int ans=0;
        ans=koo/2;
        for(i=1;i<(int)vv.size();i++){
            int j=i-1;
            int a=vv[j].second,b=vv[i].second;
            string sa=vv[j].first,sb=vv[i].first;
            int cpl;
            cpl=cplen(sa,sb);
            if(abs(a-b)>=cpl)
                ans=max(ans,cpl);
            }
        printf("%d\n",ans);
        }
    return 0;
    }

複雑さ : O(n*log(n)) (ソートによる)

于 2016-03-25T20:41:20.823 に答える
0

これは、「Computing Longest Previous non-overlapping Factors」に示されている結果を使用して解決できます ( http://dx.doi.org/10.1016/j.ipl.2010.12.005を参照) 。

于 2013-09-25T18:46:34.367 に答える