Java编程任务效率

Question

我正在努力学习编写更高效的代码。你们中的一些天才开发人员是否有机会帮助我并让我知道我的代码哪里出了问题？如何才能提高效率？

我刚刚在 Codility.com 上完成了一项任务，并且通过了所有测试，但是当传入较大的字符串时，我的代码效率不够高。

任务描述:

A prefix of a string S is any leading contiguous part of S. For example, "c" and "cod" are prefixes of the string "codility". For simplicity, we require prefixes to be non-empty. The product of prefix P of string S is the number of occurrences of P multiplied by the length of P. More precisely, if prefix P consists of K characters and P occurs exactly T times in S, then the product equals 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.

最长的前缀与原始字符串相同。目标是选择能够最大化产品值(value)的前缀。在上面的示例中，最大乘积为 10。

在此问题中，我们仅考虑由小写英文字母 (a-z) 组成的字符串。

编写一个函数

class Solution { public int solution(String S); }

给定一个由 N 个字符组成的字符串 S，返回给定字符串的任何前缀的最大乘积。如果乘积大于 1,000,000,000，该函数应返回 1,000,000,000。

例如，对于字符串:

S = "abababa" the function should return 10, as explained above,

S = "aaa" the function should return 4, as the product of the prefix "aa" is maximal.

假设:

N is an integer within the range [1..300,000];

string S consists only of lower-case letters (a-z).

复杂性:

预期最坏情况时间复杂度为 O(N)；

预计最坏情况的空间复杂度为 O(N)(不计算输入参数所需的存储空间)。

这是我失败的结果:

easy_morphism a -> a?a 2.150 s. TIMEOUT ERROR running time: >2.15 sec. large_random_string cyclic + random string 1.180 s. TIMEOUT ERROR running time: >1.18 sec.

large_cyclic large cyclic tests 2.170 s. TIMEOUT ERROR running time: >2.17 sec.

single_letter_with_some_tweaks 2.170 s. TIMEOUT ERROR running time: >2.17 sec.

same_small_pattern_with_small_tweaks 2.160 s. TIMEOUT ERROR running time: >2.16 sec.

same_big_pattern_with_small_tweaks 4.660 s. TIMEOUT ERROR running time: >4.66 sec.

small_pattern_with_tweaks_in_one_place 4.700 s. TIMEOUT ERROR running time: >4.70 sec.

任何帮助或提示都会很方便!

public class test {

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        System.out.println("solution: " + solution("abababa"));
        long endTime = System.nanoTime();

        long duration = endTime - startTime;
        System.out.println("duration: " + duration/1000000.0 + " seconds");
    }

    public static int solution(String S) {
        int solution = 0, N = S.length();
        String P;
        for (int K = 1; K <= N; K++) {
            P = S.substring(0, K);

            int T = calculateT(P, S);

            int tmpSolution = K * T;
            if (tmpSolution > solution) {
                solution = tmpSolution;
            }
        }

        return solution;
    }

    public static int calculateT(String P, String S) {
        int T = 0, indexOfStart = 0;

        while (indexOfStart > -1) {
            T++;
            indexOfStart = S.indexOf(P, indexOfStart+1);
        }

        return T;
    }
}

Answer 1

经过一番搜索，我最终找到了一些解决方案。感谢@afk5min 的建议。

我还建议阅读有关 Z 算法的内容: http://codeforces.com/blog/entry/3107

还有 KMP 算法:http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

我认为我需要学习的提高效率的主要方法是不要嵌套循环。如果代码进入一个循环，然后进入另一个循环，它会突然消耗更多时间，并且扩展效率变得低下。

我需要开始思考我的算法的方式是，遍历某些东西几次以获得最终结果是可以的。这样做比将循环嵌套在循环中要好得多。