用于匹配任意长度的所有重复子字符串的Regex表达式

Question

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

我想用regex来识别在这个字符串中重复的所有子字符串(即没有强制迭代循环)。

对于上面的字符串，结果集是：{"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'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%的改进版本：

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

Answer 2

无法在单个正则表达式中获得所需的结果，因为正则表达式要么贪婪地匹配(查找bc...bc)，要么懒惰地匹配(查找b...b和c...c)，但两者都不匹配。(在您的示例中，它确实找到了c...c，但这只是因为c被重复了两次。)

但是，一旦找到长度大于1的重复子字符串，那么所有较小的“该子字符串的子字符串”也必须重复。如果你想把它们拼出来，你需要分开做。

以您的例子为例(使用Python，因为我不知道PHP)：

>>> results = set(m.group(1) for m in re.finditer(r"(?=(.+).*\1)", "abcbcdcde"))
>>> results
{'d', 'cd', 'bc', 'c'}

然后，您可以将以下函数应用于每个结果：

def substrings(s):
    return [s[start:stop] for start in range(len(s)-1) 
                          for stop in range(start+1, len(s)+1)]

例如：

>>> substrings("123456")
['1', '12', '123', '1234', '12345', '123456', '2', '23', '234', '2345', '23456',
 '3', '34', '345', '3456', '4', '45', '456', '5', '56']

Answer 3

我能得到的最接近的是/(?=(.+).*\1)/

查找的目的是允许多次匹配相同的字符(例如，c和cd)。然而，由于某些原因，它似乎没有得到b.