PHP 计算字符串出现次数的最快方法是什么？ [关闭]

字符串 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) 组成的字符串。 写一个函数

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).

复杂：

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

到目前为止我的代码：

function solution($S) {
    $PROD = 0;
    for ($i=1; $i <= strlen($S); $i++){
        $p = substr($S, 0, $i);
        $counter = 0;
        $offset = 0;
        $pos = strpos($S, $p, $offset);
        while($pos !== false) { 
            $counter++;
            $offset = $pos + 1;            
            $pos = strpos($S, $p, $offset);
        }
        if ($PROD < ($counter * strlen($p))){
            $PROD = $counter * strlen($p);
            if ($PROD > 1000000000)
                return 1000000000;
        }
    }
    return $PROD;
}

有什么办法可以做得更快吗？

我认为你必须制定自己的功能。这就是我要做的：

The demo http://codepad.org/LSpTq0g4

function substr_count_overlap($string, $needle) {
    $count = 0;
    $start = 0;
    while(1) {
        $found = strpos($string, $needle, $start);
        if($found !== FALSE) {
            $count++;
            $start = $found + 1;
        } else return $count;
    }
    return $count;
}

并以这种方式使用它：

$myString = 'aaa';
$search = 'aa';

echo substr_count_overlap($myString, $search);

由于这一行，速度更快：

$start = $found + 1;

您不会将整个字符串 1 个字符按 1 走，而是直接跳到下一个出现的位置。