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 <-- ouch!

当你看到24k字节(或真正高于1k的任何东西)时,它会变得更奇怪：

Pure PHP      - 4.565s (10 runs)
PCRE          - 0.232s <-- WAT?!

事实证明,正则表达式在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,$i)) {
                    break;
                }
                $res[$pat] = 1;
            }
            // expand pattern and try again
            $pat .= $s[$i++];
        }
    }
    return array_keys($res);
}