1

我的问题如下，我想在一个字符串中找到所有出现的子字符串。更具体地说，我想找到所有索引集，s[0]...s[n]以便字符串是否与所寻找的子st字符串匹配。st[s[0]], st[s[1], ... st[s[n]]“但为什么？？” 你问，嗯......因为它在代码堵塞上。通过对所有可能的排列进行顺序比较很容易解决，但是对于大字符串来说它会变慢。所以我想到了正则表达式。

例如，对于字符串 'abcoeubc' 和子字符串 'abc' 它应该给我索引 [(0,1,2),(0,1,7),(0,6,7)] 或其他之类的。我真的不想要索引，而只是为了计算子出现的数量。我一直在尝试类似的东西

import re
r = re.compile(r'a.*b.*c')
matches = [m for i in r.finditer('abcoeubc')]

但它的表现并不像我预期的那样。我也尝试过使用前瞻表达式，类似r = re.compile(r'(?=a).*(?=b).*(?=c)')但也不起作用。尝试为此使用正则表达式我错了吗？

4

2 回答 2

3

编辑

子编辑：添加了一些多汁的低挂水果。稍微模糊，明显更快。

你要速度吗？

超速？

出色地...

from bisect import bisect_right

def count_ascending_permutations(sequence_indexes, i, max=float("inf")):
    last = sequence_indexes[i]
    end = bisect_right(last, max)

    return sum(
        count_ascending_permutations(sequence_indexes, i-1, item)
        for item in last[:end]
    ) if i else end

def count_allpaths(target, sequence):
    sequence_chars = {k: [] for k in sequence}
    for i, character in enumerate(target):
        if character in sequence_chars:
            sequence_chars[character].append(i)

    sequence_indexes = [sequence_chars[character] for character in sequence]

    return count_ascending_permutations(sequence_indexes, len(sequence_indexes)-1)

您不能使用 Regex 执行此操作，因为 Regex 不会查找所有可能的匹配项，仅显示位置与您正在搜索的 Regex 匹配。

这是一个解决方案，我将更新解释：

from itertools import takewhile

def ascending_permutations(sequence_indexes, i, max=float("inf")):
    last = takewhile(lambda item: item < max, sequence_indexes[i])

    if i == 0:
        for item in last:
            yield [item]

    for item in last:
        for subitems in ascending_permutations(sequence_indexes, i-1, item):
            subitems.append(item)
            yield subitems

def allpaths(target, sequence):
    sequence_indexes = []
    for character in sequence:
        sequence_indexes.append([i for i, c in enumerate(target) if c == character])

    return ascending_permutations(sequence_indexes, len(sequence_indexes)-1)

list(allpaths("abcoeubcbc", "abc"))
#>>> [[0, 1, 2], [0, 1, 7], [0, 6, 7], [0, 1, 9], [0, 6, 9], [0, 8, 9]]

足够的编辑，解释！

如果您有字符abcoeubcbc并且想要从中abc按顺序排列字符，那么您正在查看

0123456780
abcoeubcbc
----------
abc       
ab     c  
a     bc  
ab       c
a       bc

与其往前读（这是显而易见的解释），不如往后读。

看看它们在哪里c。它依次位于位置 2、7 和 0。

当它位于位置 0 时，您可以忽略它之后的所有内容，因为它们会是无序的：

012
abc
---
abc

并为b. 好吧，它只有一个位置，对于 也是a如此，所以这很容易。进入下一部分：

01234567
abcoeubc
--------
ab     c
a     bc

b可以去两个地方。在这两种情况下a都有一个插槽。

然后对于最终位置：

0123456780
abcoeubcbc
----------
ab       c
a       bc

再次b有两个位置，然后我们对每个位置进行递归，并且a只有一个位置。

在我深切饥饿之后，更多关于这与下面的代码的关系！

我回来了，比我预期的晚了一点。不急，我猜，因为 OP 甚至似乎都没有注意到我......

首先我们应该看看allpaths。

def allpaths(target, sequence):
    sequence_indexes = []
    for character in sequence:
        sequence_indexes.append([i for i, c in enumerate(target) if c == character])

    return ascending_permutations(sequence_indexes, len(sequence_indexes)-1)

allpaths是一个包装函数——它实际上并没有实现太多，除了为ascending_permutations. 这是必需的，因为正如您稍后将看到的那样，ascending_permutations它是递归的，我们只想运行这部分。

首先，

for character in sequence:
    sequence_indexes.append([i for i, c in enumerate(target) if c == character])

为每个字符生成单词中每次出现的索引。这是一个“矩阵”，因为它是一个列表列表：

  abcoeubcbc
  ----------
a|0         |  →  [[0,     ],
b| 1    6 8 |  →   [1, 6, 8],
c|  2    7 9|  →   [2, 7, 9]]
  ----------

当前方法采用O(len(target) × len(sequence))，这可以O(len(target) + len(sequence))通过使用字典进行优化：

sequence_chars = {k: [] for k in sequence}
for i, character in enumerate(target):
    if character in sequence_chars:
        sequence_chars[character].append(i)

sequence_indexes = [sequence_chars[character] for character in sequence]

这很酷，我想。

然后它将这个矩阵发送到ascending_permutations，它会做实际的工作。

ascending_permutations从列表的末尾向后工作。这听起来可能很奇怪，但这是一个有根据的结构。

假设您有阶乘的递归算法：

def fact(n):
    if n == 1:
        return n

    return n * fact(n-1)

调用fact(3)确实如此fib(3) == 3 * fib(2) == 3 * (2 * fib(1)) == 3 * (2 * (1))，我们可以看到1 → 2 → 3，由于括号，我们从乘法开始向外工作。因为我们想用append它来构建我们的列表（它快append，慢insert(0, item)）我们想做：

(((our_list).append(a's position)).append(b's position)).append(c's position)

所以我们可以看到最外面的范围是c，不是a。因此我们应该从a.

我们也传递len(sequence_indexes)-1到，ascending_permutations因为我们不想继续poping 项目并将它们推回；我们将递归进出，并且更容易跟踪我们认为“结束”在哪里。len(sequence_indexes)-1是 中最后一项的位置，在这种情况下sequence_indexes是索引的数量。c

所以，现在开始讨论函数的内容......

def ascending_permutations(sequence_indexes, i, max=float("inf")):

max跟踪不同类型的结束；wheresi跟踪字母，max跟踪要搜索的最高索引：

     max→

     abcoeubcbc
     ----------
i  a|0         |  →  [[0,     ],
↓  b| 1    6 8 |  →   [1, 6, 8],
   c|  2    7 9|  →   [2, 7, 9]]
     ----------

然后我们要遍历我们的“活动”字母，也就是最后一个：

    last = takewhile(lambda item: item < max, sequence_indexes[i])

请注意，我们使用takewhile将数字裁剪为max，因此没有索引超过或超过我们之前计算的字母。max以无穷大开始，因此在您选择字母之前没有限制！

然后我们有一个结束条件：

    if i == 0:
        for item in last:
            yield [item]

基本上这就是说，如果你只有一个字母，那么你的“路径”就是这封信的索引。

最后，我们处于递归的核心。

对于我们的字母所在的每个索引，我们需要单独递归。对于c，我们递归到索引和2，例如。79

    for item in last:

然后我们需要获取我们“裁剪”数量的所有路径。

        for subitems in ascending_permutations(sequence_indexes, i-1, item):

记住这一点：

01234567
abcoeubc
--------
ab     c
a     bc

? 这就是递归所做的：它采用给定特定位置的子集c（在这种情况下7）并将问题简化为该部分。

现在我们有了那个子部分的列表，我们可以将我们的位置（在这个例子7中，记住）添加到最后并抛出结果“上游”。

            subitems.append(item)
            yield subitems

而已。很简单吧？

于 2013-09-23T15:41:31.920 回答
0

所以这就是我在没有正则表达式的情况下解决它的方法，但是对于大输入来说它真的很慢。我会尝试检查替代实现......

import re
def simple_match( string, pattern ):
    count = 0
    # if there's only one character left, return the number of occurrences
    if len(pattern)==1:
        return len(re.findall( pattern, string ) )
    # otherwise find all occurrences of the first char of the remaining string
    pos = [i.start() for i in re.finditer( pattern[0], string )]
    # and for each position
    for i in pos:
        # check if the next char still comes up in the remaining string
        next2 = re.search( pattern[1], string[i:])
        # if it doesn't it, there are no valid substrings remaining, so break
        if next2 is None:
            break
        # else recur with the remaining string and pattern
        count+=simple_match( string[(i+1):], pattern[1:] )
    return count

可能效率较低，但实际上不明白为什么。

于 2013-09-24T08:20:43.873 回答