[codility]PrefixMaxProduct

Codility Certificate题目。求product最大值，product为长度*出现次数，例子"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.

这道题要用到KMP算法，所以研究了半天。http://www.cnblogs.com/lautsie/p/3228877.html 根据我们从-1开始的next数组是[-1, 0, 0, 1, 2, 3, 4, 5]，注意这里我们最后有个5，比普通的next数组多一个。所以这里的while条件改成了i < s.size()

比如这里的3表示，abababa和abababa有3个是重合的。这样我们可以从后往前计数，如果某个字符数到了，就把它的next[i]的count加上。以aba举例：

abababa和abababa 时，给第三个a加了1，

abababa和abababa时，给第二个a加了1，这时，这个a的count是3。

#include <vector>

int solution(string &s) {

    // write your code in C++98

    vector<int> next(s.size()+1, 0);

    vector<int> counter(s.size()+1, 1);

    // build next array

    int i = 0;

    int j = -1;

    next[0] = -1;

    while (i < s.size()) {

        if (j == -1 || s[i] == s[j]) {

            next[++i] = ++j;

        }

        else {

            j = next[j];

        }

    }

    int ans = 0;

    for (int i = s.size(); i > 0; i--) {

        ans = max(ans, i * counter[i]);

        if (ans > 1000000000) return 1000000000;

        if (next[i] >= 0)

            counter[next[i]] += counter[i];

    }

    return ans;

}