用于匹配任何长度的所有重复子串的正则表达式

Question

假设我们有一个字符串: "abcbcdcde"

我想使用正则表达式识别在该字符串中重复的所有子串(即没有暴力迭代循环).

对于上面的字符串,结果集将是: {"b","bc","c","cd","d"}

我必须承认,对于有经验的人来说,我的正则表达式应该比它应该更加生疏.我尝试使用反向引用,但这只会匹配连续的重复项.我需要匹配所有重复项,连续或其他.

换句话说,我想匹配> =第二次出现的任何字符.如果子串出现5次,那么我想捕获每个出现2-5.合理？

到目前为止,这是我可悲的尝试:

preg_match_all( '/(.+)(.*)\1+/', $string, $matches );  // Way off!

我试着玩前瞻,但我只是在屠杀它.我在PHP(PCRE)中这样做,但问题或多或少与语言无关.我发现自己对此感到困惑,这有点令人尴尬.

Answer 1

你的问题是递归的...你知道吗,忘了递归!= 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的答案:

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的回答的帮助下,我整理了一个改进版本,在优化以下内容后,性能提高了约18%:

1. 删除substr()外部循环中的调用以推进字符串指针; 这是我之前的递归化身遗留下来的.

2. 将部分结果用作正缓存以跳过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);
}