PHP计算字符串出现次数最快的方法是什么? [英] PHP What is the fastest way to count strings occurrences?

问题描述

字符串S的前缀是S的任何前导连续部分.例如，"c"和"cod"是字符串"codility"的前缀.为简单起见，我们要求前缀为非空.字符串S的前缀P的乘积是P的出现次数乘以P的长度.更准确地说，如果前缀P由K个字符组成并且P在S中恰好出现了T次，则乘积等于K *T.例如，S ="abababa"具有以下前缀:

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. For example, S = "abababa" has the following prefixes:

"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.在此问题中，我们仅考虑由小写英文字母(az)组成的字符串.编写函数

The longest prefix is identical to the original string. The goal is to choose such a prefix as maximizes the value of the product. In above example the maximal product is 10. In this problem we consider only strings that consist of lower-case English letters (a−z). Write a function

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

，给定一个包含N个字符的字符串S，它返回给定字符串的任何前缀的最大乘积.如果乘积大于1,000,000,000，则该函数应返回1,000,000,000.例如，对于一个字符串:

that, given a string S consisting of N characters, returns the maximal product of any prefix of the given string. If the product is greater than 1,000,000,000 the function should return 1,000,000,000. For example, for a string:

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

到目前为止，我的代码:

My code so far:

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;
}

有什么方法可以更快地完成它?

is there any way to do it more faster ?

推荐答案

我认为您将必须执行自己的功能.这就是我的方法:

I think you will have to make your own function. This is how I would make it :

演示

The demo

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

由于此行，因此速度更快:

This is faster because of this line :

$start = $found + 1;

您不会将整个字符串按1个字符移动1个字符，而是直接进入下一个出现的位置.

You don't walk the entire string 1 char by 1, but you step directly to the next occurence.

这篇关于PHP计算字符串出现次数最快的方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！