1

2 つの文字列 A と B について、文字列の類似性を、両方の文字列に共通する最長のプレフィックスの長さと定義します。たとえば、文字列 "abc" と "abd" の類似度は 2 ですが、文字列 "aaa" と "aaab" の類似度は 3 です。文字列 S とその接尾辞のそれぞれの類似度の合計を計算します

これが私の解決策です...

#include<stdio.h>
#include<string.h>
int getSim(char str[],int subindex)
{
    int l2=subindex
    int i=0;
    int count=0;
    for(i=0;i<l2;i++)
        if(str[i]==str[subindex])
        {
            count++;
            subindex++;
        }
        else
            break;
    return count;   
}
int main()
{
    int testcase=0;
    int len=0;
    int sum=0;
    int i=0;
    char s[100000];
    scanf("%d",&testcase);
    while(testcase--)
    {
        sum=0;
        scanf("%s",s);
        for(i=0;i<strlen(s);i++)
            if(s[i]==s[0])
            {
                sum=sum+getSim(s,i);
            }
        printf("%d\n",sum);
    }
}

接尾辞配列を使用してこの問題を解決するにはどうすればよいでしょうか??

4

2 に答える 2

2

それが最良のアルゴリズムかどうかはわかりませんが、ここに解決策があります。

まず、接尾辞配列を構築します。単純なアルゴリズム (すべての接尾辞を配列に入れてから並べ替える) は非常に遅く、O(n^2 * log(n)) 操作です。O(nlogn) 時間でこれを行うアルゴリズムがいくつかあります。

文字列のインデックスは 0 であると想定しています。

  1. ここでl、文字列 の最初の文字を取得し、1sつのバイナリ検索を使用iして、接尾辞配列内の で始まる最初の文字列lのインデックスを見つけ、別のバイナリ検索をj使用して範囲 [i..n の最初の文字列のインデックスを見つけます。 ] で始まりませんl。次に、範囲 [i..j-1] 内のすべての文字列が同じ文字で始まることがわかりlます。したがって、問題の答えは少なくとも ji です。

  2. 次に、範囲 [i..j) の文字列に同様の手順を適用します。2 番目の文字を取り、そのような最初の文字列とそのような最初の文字列に対応するl2インデックスi2とを見つけます。答えに j2-i2 を追加します。j2s[i2]s[i2][1] == l2s[j2]s[j2][1] != l2

  3. 元の文字列の文字がなくなるまで、この手順を n 回繰り返します。問題の答えは j1-i1 + j2-i2 + ... + jn-in

于 2012-01-15T10:16:08.317 に答える
1

あなたはそれが正しいとコメントで述べていますが、それは非常に遅いです。

StringJavaでは、 withの長さを取得できます。s.length()この値はオブジェクトにキャッシュされ、O(1)取得することになります。

しかし、Cに移動すると、毎回strlen(s)（で）再計算される文字列の長さがわかります。O(n)したがって、実行する必要がある間、そこに操作があるO(n)ためO(n)、関数全体がになりO(n^2)ます。

これを回避するには、実行時に値を1回キャッシュします。これにより、線形時間に戻ります。

悪い：

scanf("%s",s);
for(i=0;i<strlen(s);i++)
    if(s[i]==s[0])
    {
        sum=sum+getSim(s,i);
    }

良い：

scanf("%s",s);
strlen = strlen(s); /* assume you declared "int strlen" earlier */
for(i=0;i<strlen;i++) /* this is now constant time to run */
    if(s[i]==s[0])
    {
        sum=sum+getSim(s,i);
    }
于 2012-01-15T09:55:01.703 に答える