3

最新の Codility を完了し、合格しましたが、100% 取得できませんでした

スペックはこちら

文字列 S のプレフィックスは、S の先頭の連続部分です。たとえば、「c」と「cod」は文字列「codility」のプレフィックスです。簡単にするために、プレフィックスは空ではない必要があります。文字列 S のプレフィックス P の積は、P の出現回数に P の長さを掛けたものです。より正確には、プレフィックス P が K 文字で構成され、P が S 内でちょうど T 回出現する場合、積は K * T に等しくなります。

たとえば、S = "abababa" には次の接頭辞があります。

"a", whose product equals 1 * 4 = 4,
"ab", whose product equals 2 * 3 = 6,
"aba", whose product equals 3 * 3 = 9,
"abab", whose product equals 4 * 2 = 8,
"ababa", whose product equals 5 * 2 = 10,
"ababab", whose product equals 6 * 1 = 6,
"abababa", whose product equals 7 * 1 = 7.

最長のプレフィックスは元の文字列と同じです。目標は、製品の価値を最大化するような接頭辞を選択することです。上記の例では、最大積は 10 です。この問題では、小文字の英字 (a-z) で構成される文字列のみを考慮します。

つまり、基本的には文字列トラバースの問題です。すべての検証パートに合格できましたが、時間内に負けてしまいました。これが私が書いたものです

int Solution(string S)
{
     int finalCount = 0;

        for (int i = 0; i <= S.Length - 1; i++)
        {
            string prefix = S.Substring(0, i + 1);
            int count = 0;
            for (int j = 0; j <= S.Length - 1; j++)
            {
                if (prefix.Length + j <= S.Length)
                {
                    string newStr = S.Substring(j, prefix.Length);
                    if (newStr == prefix)
                    {
                        count++;
                    }
                }
                if (j == S.Length - 1)
                {
                    int product = count * prefix.Length;
                    if (product > finalCount)
                    {
                        finalCount = product;
                    }
                }
            }
         }
           return  finalCount;
}

ネストされたループが私を殺していることは知っていますが、他のループを追加せずに文字列の「セクション」をトラバースする方法は考えられません。

どんな助けでも大歓迎です。

4

4 に答える 4

4

単純な力ずくの解決には O(N ** 3) の時間がかかります。1 から N までの長さを選択し、その長さのプレフィックスを取得し、ブルート フォース検索によって出現回数をカウントします。長さの選択には O(N) 時間、ブルート フォースには O(N ** 2) 時間、合計で O(N ** 3) かかります。KMP や Z-algo を使用すると、O(N) 時間で出現を見つけることができるため、全体の解は O(N ** 2) 時間になります。

また、発生を事前計算できるため、O(N) + O(N) = O(N) 時間のソリューションが必要になります。

vector<int> z_function(string &S); //z-function, z[0] = S.length()

vector<int> z = z_function(S);
//cnt[i] - count of i-length prefix occurrences of S
for (int i = 0; i < n; ++i) 
  ++cnt[z[i]];

 //if cnt[i] is in S, cnt[i - 1] will be in S
 int previous = 0;
 for (int i = n; i > 0; --i) {
  cnt[i] += previous;
  previous = cnt[i];
 }

すべての O(N ** 3)、O(N ** 2)、O(N) ソリューションを説明するブログ投稿は次のとおりです。

于 2013-11-13T12:27:40.057 に答える
1

私の努力は次のとおりで、不要な文字列比較を排除しようとしました。isaacs ブログを読みましたが、これが c# にどのように変換されるかは c にあります。文字列の不変性要因を回避するためにどこでも配列を使用することさえしましたが、改善はありませんでした。

        int Rtn = 0;
        int len = S.Length;

        if (len > 1000000000)
            return 1000000000;

        for (int i = 1; i <= len; i++)
        {
            string tofind = S.Substring(0, i);
            int tofindlen = tofind.Length;
            int occurencies = 0;

            for (int ii = 0; ii < len; ii++)
            {
                int found = FastIndexOf(S, tofind.ToCharArray(), ii);
                if (found != -1)
                {
                    if ((found == 0 && tofindlen != 1) || (found >= 0))
                    {
                        ii = found;
                    }
                    ++occurencies ;
                }
            }
            if (occurencies > 0)
            {
                int total = occurencies * tofindlen;

                if (total > Rtn)
                {
                    Rtn = total;
                }
            }
        }
        return Rtn;
    }


    static int FastIndexOf(string source, char[] pattern, int start)
    {

        if (pattern.Length == 0) return 0;
        if (pattern.Length == 1) return source.IndexOf(pattern[0], start);
        bool found;
        int limit = source.Length - pattern.Length + 1 - start;
        if (limit < 1) return -1;

        char c0 = pattern[0];
        char c1 = pattern[1];
        // Find the first occurrence of the first character
        int first = source.IndexOf(c0, start, limit);

        while ((first != -1) && (first + pattern.Length <= source.Length))
        {
            if (source[first + 1] != c1)
            {
                first = source.IndexOf(c0, ++first);
                continue;
            }
            found = true;
             for (int j = 2; j < pattern.Length; j++)
                if (source[first + j] != pattern[j])
                {
                    found = false;
                    break;
                }
            if (found) return first;
            first = source.IndexOf(c0, ++first);
        }
        return -1;
    }
于 2013-11-25T18:29:13.873 に答える
0

私は43しか持っていません...私は私のコードが好きです！JavaScript の同じスクリプトは、その価値に対して 56 を得ました。

using System;

class Solution
{
    public int solution(string S)
    {

    int highestCount = 0;

    for (var i = S.Length; i > 0; i--)
    {
        int occurs = 0;
        string prefix = S.Substring(0, i);    
        int tempIndex = S.IndexOf(prefix) + 1;             
        string tempString = S;            

        while (tempIndex > 0)
        {
            tempString = tempString.Substring(tempIndex);
            tempIndex = tempString.IndexOf(prefix);                                
            tempIndex++;
            occurs++;                                          
        }

        int product = occurs * prefix.Length;

        if ((product) > highestCount)
        {
            if (highestCount >  1000000000)              
                return 1000000000;                           
            highestCount = product;
        }
    }

    return highestCount;

}

}
于 2013-12-09T10:09:48.993 に答える