在Python中查找一个字符串在另一个字符串中的多次出现

Question

我正在尝试查找一个字符串是否存在于另一个字符串中，不使用Python的预定义函数，例如find和index。

目前我的函数有两个参数，其中一个是我们要搜索的字符串，另一个字符串是我们要在第一个字符串中寻找的内容。

如果第二个字符串存在于第一个字符串中，我希望我的函数返回它在第一个字符串中出现的所有位置。

目前，我的函数能够找到第一次出现并返回索引，但我想找到多个出现而不仅仅是第一个。

以下是我的代码：

def multi_find (s, r):

    s_len = len(s)
    r_len = len(r)

    if s_len < r_len:
        n = -1
    else:
        m = s_len - r_len
        n = -1  # assume r is not yet found in s
        i = 0

        while n == -1 and i < m:
            # search for r in s until not enough characters are left
            if s[i:i + r_len] == r:
                n = i
            else:
                i = i + 1
    print (n)

multi_find("abcdefabc. asdli! ndsf acba saa abe?", "abc")

现在，输出的结果只是“0”，因为那里是第一次出现 abc 的位置。我该如何让它返回“0”和“6”（第二次出现的开头）？也就是说，在找到一个之后继续检查。

我想到了一种方法，就是创建一个包含所有出现位置的列表，然后将 i 添加到该列表中，但是当我尝试这样做时，没有成功。

- l00kitsjake

Answer 1

你可以做以下操作：

>>> haystack = "abcdefabc. asdli! ndsf acba saa abe?"
>>> needle = "abc"
>>> for i, _ in enumerate(haystack):
...     if haystack[i:i + len(needle)] == needle:
...         print (i)
...
0
6

- Simeon Visser

---

你能解释一下在 'for i, _ in enumerate(haystack):' 这一行中的"_"吗？我不太确定它的作用是什么。 - l00kitsjake

@JacobMammoliti：这意味着您正在忽略那里的变量。enumerate()允许您迭代字符串的位置和字符，但我们没有使用字符。因此，我们只是在迭代字符串中的每个位置。您还可以编写for i, c in enumerate(haystack):以同时迭代字符串的每个位置i和每个字符c。 - Simeon Visser

请注意，"_"只是一种约定，旨在使人类读者清楚地理解代码 - 它与使用"x"没有任何不同。 - neil

Answer 2

使用正则表达式的另一种替代方法：

>>> import re
>>> haystack = "abcdefabc. asdli! ndsf acba saa abe?"
>>> needle = "abc"
>>> [m.start() for m in re.finditer(r'{}'.format(re.escape(needle)), haystack)]
[0, 6]

上述解决方案对于重叠的子字符串不起作用，例如在 'aaaa' 中有 3 个 'aa'。因此，如果您还想查找重叠的匹配项，则：

>>> haystack = "bobob"
>>> needle = "bob"
>>> [m.start() for m in re.finditer(r'(?={})'.format(re.escape(needle)), haystack)]
[0, 2]

- Ashwini Chaudhary

---

我喜欢使用re，但由于目标是“返回它在第一个字符串中出现的所有位置”，我认为这种方法无法找到一些有趣的情况，其中r在s中多次出现，但其实例重叠。考虑这种情况：multi_find("bobob","bob")。使用您的实现，字符串“bob”肯定出现在“bobob”的位置2，但未被返回。我喜欢这个一行代码，但我想抛出这个可能的问题。这可能对@Jacob无关紧要。 - Darren Stone

@DarrenStone 很好的观点，我添加了另一个解决方案，可以处理重叠匹配。 - Ashwini Chaudhary

Answer 3

def multi_find(s, r):

    s_len = len(s)
    r_len = len(r)

    _complete = []

    if s_len < r_len:
        n = -1
    else:

        for i in xrange(s_len):
            # search for r in s until not enough characters are left
            if s[i:i + r_len] == r:
                _complete.append(i)
            else:
                i = i + 1
    print(_complete)

multi_find("abcdefabc. asdli! ndsf abc saa abe?", "abc")

- Siva Cn

Answer 4

def multi_find (s, r):
    s_len = len(s)
    r_len = len(r)
    n = [] # assume r is not yet found in s

    if s_len >= r_len:
        m = s_len - r_len
        i = 0

        while i < m:
            # search for r in s until not enough characters are left
            if s[i:i + r_len] == r:
                n.append(i)
            i = i + 1
    print (n)

multi_find("abcdefabc. asdli! ndsf acba saa abe?", "abc")

基本上只需将n替换为列表，以便您在找到值时可以继续向其中添加值。即使找到匹配项，您也需要递增i，否则它将一直卡在循环中，除非您有while n == -1的约束条件，该条件使其在找到匹配项后立即停止。

- OGHaza

Answer 5

最好的方法可能是不断调用查找函数（这也是最快的）。

def multifind(string, value, start = 0, stop = None):
    values = []
    while True:
        found = string.find(value, start, stop)
        if found == -1:
            break
        values.append(found)
        start = found + 1
    return values

print multifind('hello abc abc', 'abc')

输出：

[6, 10]

- vitiral

---

我知道现在评论有点晚了，8年后，但问题是关于如何在不调用预定义函数（如find()）的情况下完成此操作，因此这不是按照所提问的问题的答案。 - joanis

Answer 6

@Jacob，我希望你会发现这篇文章非常简短，但仍然易于理解。

def multi_find(s, r):
    return [pos for pos in range(len(s)) if s.startswith(r,pos)]

- Darren Stone

Answer 7

注意：我认为这个答案仍然是一个很好的“教学答案”，我已经在这个线程的其他地方提交了一个更好的解决方案，没有使用递归。

def multi_find(s, r, start=0):
    if start >= len(s): 
        return []
    if s.startswith(r, start):
        return [start] + multi_find(s, r, start+1)
    else:
        return multi_find(s, r, start+1)

这允许您传递一个可选的start位置，以便在s中开始搜索。

此解决方案是递归的，这可能不是最快的实现方式，但它是正确的，我相信它使代码易于在每个s位置识别每个三种可能性：

1. s的结尾
2. 找到另一个r
3. 没有找到另一个r

- Darren Stone