你的问题是递归的…你知道吗,忘了递归！ = p它在PHP中不会很好用,如果没有它,算法也很清楚.
function find_repeating_sequences($s)
{
$res = array();
while ($s) {
$i = 1; $pat = $s[0];
while (false !== strpos($s, $pat, $i)) {
$res[$pat] = 1;
// expand pattern and try again
$pat .= $s[$i++];
}
// move the string forward
$s = substr($s, 1);
}
return array_keys($res);
}
出于兴趣,我用PHP写了Tim’s answer：
function find_repeating_sequences_re($s)
{
$res = array();
preg_match_all('/(?=(.+).*\1)/', $s, $matches);
foreach ($matches[1] as $match) {
$length = strlen($match);
if ($length > 1) {
for ($i = 0; $i < $length; ++$i) {
for ($j = $i; $j < $length; ++$j) {
$res[substr($match, $i, $j - $i + 1)] = 1;
}
}
} else {
$res[$match] = 1;
}
}
return array_keys($res);
}
我让他们在800字节随机数据的小基准测试中解决它：
$data = base64_encode(openssl_random_pseudo_bytes(600));
每个代码运行10轮,并测量执行时间.结果？
Pure PHP - 0.014s (10 runs)
PCRE - 40.86s
当你看到24k字节(或真正高于1k的任何东西)时,它会变得更奇怪：
Pure PHP - 4.565s (10 runs)
PCRE - 0.232s
事实证明,正则表达式在1k个字符之后崩溃,因此$matches数组为空.这些是我的.ini设置：
pcre.backtrack_limit => 1000000 => 1000000
pcre.recursion_limit => 100000 => 100000
我不清楚在只有1k个字符之后是如何命中回溯或递归限制的.但即使这些设置以某种方式“修复”,结果仍然很明显,PCRE似乎不是答案.
我想用C语写这个会加速它,但我不确定程度如何.
更新
在hakre’s answer的帮助下,我整理了一个改进版本,在优化以下内容后,性能提高了约18％：
>删除外部循环中的substr()调用以前进字符串指针;这是我之前的递归化身遗留下来的.
>将部分结果用作正缓存,以跳过内部循环内的strpos()调用.
在这里,它的一切荣耀(：
function find_repeating_sequences3($s)
{
$res = array();
$p = 0;
$len = strlen($s);
while ($p != $len) {
$pat = $s[$p]; $i = ++$p;
while ($i != $len) {
if (!isset($res[$pat])) {
if (false === strpos($s, $pat, $i)) {
break;
}
$res[$pat] = 1;
}
// expand pattern and try again
$pat .= $s[$i++];
}
}
return array_keys($res);
}
