3

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

我想使用正则表达式识别在这个字符串中重复的所有子字符串（即没有暴力迭代循环）。

对于上述字符串，结果集将是： {"b", "bc", "c", "cd", "d"}

我必须承认，对于有我经验的人来说，我的正则表达式要生锈得多。我尝试使用反向引用，但这只会匹配连续的重复项。我需要匹配所有重复的，连续的或其他的。

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

到目前为止，这是我可怜的尝试：

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

我尝试过使用前瞻，但我只是在扼杀它。我在 PHP (PCRE) 中这样做，但问题或多或少与语言无关。我发现自己被这件事难住了，这有点尴尬。

4

4 回答 4

9

你的问题是递归......你知道吗，忘记递归！=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);
}
于 2012-12-14T08:20:30.740 回答
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']
于 2012-12-14T08:19:20.810 回答
1

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

前瞻的目的是允许多次匹配相同的字符（例如，c和cd）。但是，由于某种原因，它似乎没有得到b...

于 2012-12-14T07:57:43.743 回答
1

有趣的问题。我基本上采用了Jacks answer中的功能，并尝试是否可以减少测试次数。

我第一次尝试只搜索一半的字符串，但结果证明substr每次创建要搜索的模式都太昂贵了。在 Jacks 中通过每次迭代附加一个字符来完成它的方式看起来要好得多。然后我确实没时间了，所以我无法进一步研究它。

然而，在寻找这样的替代实现时，我至少发现我想到的算法中的一些差异也可以应用于 Jacks 函数：

  1. 由于搜索已经使用偏移量完成，因此无需在每次外部迭代中剪切字符串的开头。
  2. 如果要寻找重复的主体的其余部分小于重复针，则不需要搜索针。
  3. 如果已经搜索过针头，则无需再次搜索。

    注意：这是一个内存交易。如果你有很多重复，你会使用相似的记忆。但是，如果您的重复次数确实很少，那么此变体会比以前使用更多的内存。

功能：

function find_repeating_sequences($string) {
    $result = array();
    $start  = 0;
    $max    = strlen($string);
    while ($start < $max) {
        $pat = $string[$start];
        $i   = ++$start;
        while ($max - $i > 0) {
            $found = isset($result[$pat]) ? $result[$pat] : false !== strpos($string, $pat, $i);
            if (!$result[$pat] = $found) break;
            // expand pattern and try again
            $pat .= $string[$i++];
        }
    }
    return array_keys(array_filter($result));
}

因此，只需将此视为对 Jacks 答案的补充。

于 2012-12-22T12:00:57.437 回答