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 回答
0

这效果更好

    private int MaxiumValueOfProduct(string input)
    {
        var positions = new List<int>();
        int max = 0;
        for (int i = 1; i <= input.Length; i++)
        {
            var subString = input.Substring(0, i);
            int position = 0;
            while ((position < input.Length) &&
                   (position = input.IndexOf(subString, position, StringComparison.OrdinalIgnoreCase)) != -1)
            {
                positions.Add(position);
                ++position;
            }

            var currentMax = subString.Length * positions.Count;
            if (currentMax > max) max = currentMax;
            positions.Clear();
        }

        return max;
    }
于 2015-11-24T16:34:24.317 回答