0

次の質問に対して、O（n ^ 2）よりも優れたアプローチを見つけるのに苦労しています。

たとえば、文字列が与えられますxyxxz。

次に、指定された文字列の各プレフィックスで一致する文字の総数を見つける必要があります。

ここで、文字列の可能なプレフィックスは次のとおりです。

 xyxxz : matching characters is 5
 yxxz  : matching characters is 0 (since 1st character doesnt match)
 xxz   : matching characters is 1
 xz    : matching characters is 1
 z     : matching characters is 0

これが出力になります。私は次のコードを実行しました：

cin>>str;
len=str.length();
for(i=0;i<len;i++){
    sum=0;
    k=i;
    for(int j=0;j<len;j++)
    {
        if(str[k] == str[j]){
           sum++;
           k++;
        }
        else
            break;
    }
    cout<<sum<<"  ";  //I get the output 5 0 1 1 0
}

しかし、それはO（n ^ 2）です。より良いアプローチが必要です：おそらくO（n）またはO（nlogn）。

前もって感謝します。

4

5 に答える 5

2

これは、次の手順を使用して線形時間で実行できます。

  1. サフィックス配列 SA と LCP 配列 (最長共通プレフィックス配列) を構築します。サフィックス配列は、文字列のすべてのサフィックスの辞書順にソートされたリストです（例で指定したリストに似ていますが、辞書順にソートされています。各サフィックスは元の文字列の開始位置、つまりサフィックスごとに1つの整数で表されることに注意してください） . LCP も整数の配列であり、長さはサフィックス配列と同じです。各位置 i>0 で、LCP[i] は接尾辞配列の i 番目の接尾辞が (i-1) 番目の接尾辞と共通する最長の接頭辞です。LCP[0]:=0 を設定します。

    接尾辞配列は、スキュー アルゴリズム (DC アルゴリズムとも呼ばれます) を使用して線形時間で構築できます。また、接尾辞配列と共に LCP 配列を O(n) 時間で構築することもできます。さらなるアイデアと実装については、最先端のサフィックス配列アルゴリズムに関する SO の投稿を参照してください。

  2. 接尾辞配列内の完全な文字列の位置を特定します (たとえば、整数 0 を含むエントリの接尾辞配列を線形にスキャンすることによって)。

  3. その位置から開始して、LCP 配列に沿って左右に歩き、各サフィックスが完全な文字列と共通している最長のプレフィックスを特定します。この手順については、この古い SO 投稿で詳しく説明しています。

備考これは O(n) 以上のメモリと時間を必要としないため、理論的には最適ですが、非常に複雑な手順であり、文字列が非常に長い場合にのみ実際に役立ちます。

于 2012-07-26T05:24:06.003 に答える
1

接尾辞配列を使用します。接尾辞配列DC3はO（N）時間でそれを行います。ここで、Nは元の文字列の文字数です。

于 2013-03-15T05:16:02.303 に答える
1

文字列の接尾辞ツリーを作成すると、接尾辞ツリーをたどって一致の長さを見つけることができます。最初の文字と一致しないルート ノードの子は、そのすべての子孫と同様に、ゼロの値を持ちます。次に、一致するルート ノードの子のすべての子孫は、少なくともそのエッジの一致の長さに等しい一致を持ちます。

于 2012-07-26T04:44:39.513 に答える
0 
int strcoll (register const char *s1, register const char *s2)
{
    while (*s1 == *s2++) {
        if (*s1++ == '\0') {
            return 0;
        }
    }
    return *s1 - *--s2;
}

この関数は、各文字列の最初の文字の比較を開始します。それらが互いに等しい場合、文字が異なるか、文字列の終わりを示すヌル文字に到達するまで、次のペアを続けます。

文字列間の関係を示す整数値を返します。ゼロ値は、両方の文字列が等しいことを示します。ゼロより大きい値は、一致しない最初の文字の値が str2 よりも str1 の方が大きいことを示します。ゼロ未満の値はその反対を示しま​​す。

于 2012-07-26T04:42:09.770 に答える
0

私は O 値の計算が苦手ですが、必要なものの別の実装を次に示します。少し効率が良いと思います。

cin >> str;

len=str.length();
for(i=0;i<len;i++)
{
    sum=0;
    k=0;

    while(str[k + sum] == str[i + sum])
    {
            sum++;
    }
    cout << sum ;

}
于 2012-07-26T05:14:29.753 に答える