在一个字符串中找到子字符串的第n个出现位置。

Question

这似乎很简单，但我是Python新手，想以最Pythonic的方式完成。

我想找到字符串中子字符串的第n个出现的索引。

肯定有与我想要做的相当的东西，就是

mystring.find("substring", 2nd)

如何在Python中实现这个功能?

- prestomation

---

寻找字符串的第n个出现次数？我理解为需要找到第n个出现次数所对应的索引位置？ - Mark Byers

是的，第n个出现的索引。 - prestomation

如果存在重叠的匹配，应该怎么处理？find_nth('aaaa', 'aa', 2) 应该返回1还是2？ - Mark Byers

是的！一定有办法在字符串中找到第n个子字符串的出现位置，并在第n个子字符串处拆分字符串。 - Reman

Answer 1

这是一个更符合Python风格的直接迭代解决方案的版本。

def find_nth(haystack: str, needle: str, n: int) -> int:
    start = haystack.find(needle)
    while start >= 0 and n > 1:
        start = haystack.find(needle, start+len(needle))
        n -= 1
    return start

例子：

>>> find_nth("foofoofoofoo", "foofoo", 2)
6

如果你想找到第n个重叠出现的“needle”，你可以通过增加1而不是增加“needle”的长度来实现，就像这样：

def find_nth_overlapping(haystack, needle, n):
    start = haystack.find(needle)
    while start >= 0 and n > 1:
        start = haystack.find(needle, start+1)
        n -= 1
    return start

例子：

>>> find_nth_overlapping("foofoofoofoo", "foofoo", 2)
3

这个版本比Mark的版本更易读，而且不需要拆分版本或导入正则表达式模块的额外内存。它还遵循了Python之禅中的一些规则，不像各种re方法：

1. 简单胜于复杂。
2. 扁平胜于嵌套。
3. 可读性很重要。

- Todd Gamblin

---

这个能用字符串实现吗？比如说使用find_nth(df.mystring.str, ('x'), 2)来查找第二个'x'的位置？ - Arthur D. Howland

find_nth的建议文档字符串："""在* haystack 中查找 needle 的第n次出现的索引。 当未找到第n*次出现时返回-1。""" - WhyWhat

find_nth 可以通过添加第四个参数 'start_position=0' 来支持在 haystack 中的起始位置，然后修改第一行为 start = haystack.find(needle, start_position)。 - Scott Kaiser

Answer 2

我认为 Mark 的迭代方法是通常的方式。

这里有一种使用字符串分割的替代方法，它通常对于查找相关进程非常有用：

def findnth(haystack, needle, n):
    parts= haystack.split(needle, n+1)
    if len(parts)<=n+1:
        return -1
    return len(haystack)-len(parts[-1])-len(needle)

这里有一个快速的一行代码（有些不太规范，因为你需要选择一些无法匹配到针的杂质）:

'foo bar bar bar'.replace('bar', 'XXX', 1).find('bar')

- bobince

---

第一个建议对于较长的字符串且您感兴趣的匹配在开头附近时效率非常低。它总是查看整个字符串。虽然这很聪明，但我不建议新手使用Python并想学习一种好的方法来完成此任务。 - Mark Byers

谢谢，我喜欢你的这个简洁表述。我认为它不是世界上最容易理解的东西，但也不比下面大多数人差。 - prestomation

+1 对于这个一行代码，它现在应该对我有所帮助。我一直在考虑做类似于.rfind('XXX')的等价操作，但是如果 'XXX' 在输入中后面出现了，那么这种方法就会失效。 - Nikhil

这个函数假设n = 0, 1, 2, 3, ...。如果你假设n = 1, 2, 3, 4, ...会更好。 - Happy

Answer 3

这将在字符串中查找第二个子字符串的出现。

def find_2nd(string, substring):
   return string.find(substring, string.find(substring) + 1)

编辑：我没有过多考虑性能，但快速递归可以帮助找到第n个出现的位置：

def find_nth(string, substring, n):
   if (n == 1):
       return string.find(substring)
   else:
       return string.find(substring, find_nth(string, substring, n - 1) + 1)

- Sriram Murali

---

这个能够一般化扩展以找到第n个元素吗？ - ifly6

在我看来，这是最好的答案，针对n=0的特殊情况，我做了一个小的补充。 - Jan Wilmans

我不想为了简洁而编辑这篇文章。不过我同意你的观点，n=0应该被视为一个特殊情况。 - Sriram Murali

这应该被调整以处理子字符串出现次数少于 n 的情况。（在这种情况下，返回值将周期性地通过所有出现位置循环）。 - coldfix

Answer 4

明白正则表达式并不总是最好的解决方案，我可能会在这里使用一个：

>>> import re
>>> s = "ababdfegtduab"
>>> [m.start() for m in re.finditer(r"ab",s)]
[0, 2, 11]
>>> [m.start() for m in re.finditer(r"ab",s)][2] #index 2 is third occurrence 
11

- Mark Peters

---

当然，这里的风险是搜索字符串可能包含特殊字符，这将导致正则表达式执行您不想要的操作。使用re.escape应该可以解决这个问题。 - Mark Byers

这很聪明，但它真的符合Pythonic吗？似乎为了仅查找子字符串的第n个出现而过度使用，并且不容易阅读。而且，正如你所说，你必须导入所有re。 - Todd Gamblin

当您使用方括号时，您告诉Python创建整个列表。而圆括号只会迭代第一个元素，这更有效：(m.start() for m in re.finditer(r"ab",s))[2] - emu

@emu 不，你发布的代码不会起作用；你不能获取生成器的索引。 - Mark Amery

@MarkAmery 很抱歉！我很惊讶我为什么会发布那段代码。不过，使用 itertools.islice 函数仍然有一种类似而且丑陋的解决方案：next(islice(re.finditer(r"ab",s), 2, 2+1)).start() - emu

Answer 5

我提供了一些基准测试结果，比较了迄今为止最突出的方法，即@bobince的findnth()（基于str.split()）与@tgamblin或@Mark Byers的find_nth()（基于str.find()）。我还将与C扩展程序（_find_nth.so）进行比较，以查看我们可以达到多快。这里是find_nth.py：

def findnth(haystack, needle, n):
    parts= haystack.split(needle, n+1)
    if len(parts)<=n+1:
        return -1
    return len(haystack)-len(parts[-1])-len(needle)

def find_nth(s, x, n=0, overlap=False):
    l = 1 if overlap else len(x)
    i = -l
    for c in xrange(n + 1):
        i = s.find(x, i + l)
        if i < 0:
            break
    return i

当然，如果字符串很大，性能最为重要，因此假设我们想在名为'bigfile'的1.3 GB文件中查找第1000001个换行符（'\n'）。为节省内存，我们希望使用 mmap.mmap 对象表示文件：

In [1]: import _find_nth, find_nth, mmap

In [2]: f = open('bigfile', 'r')

In [3]: mm = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)

findnth() 存在的第一个问题是，mmap.mmap 对象不支持 split()。因此，我们实际上必须将整个文件复制到内存中：

In [4]: %time s = mm[:]
CPU times: user 813 ms, sys: 3.25 s, total: 4.06 s
Wall time: 17.7 s

哎呀！幸运的是s仍适合我的Macbook Air的4 GB内存，所以让我们来测试findnth()的性能：

In [5]: %timeit find_nth.findnth(s, '\n', 1000000)
1 loops, best of 3: 29.9 s per loop

性能表现显然很糟糕。让我们看看基于str.find()的方法如何：

In [6]: %timeit find_nth.find_nth(s, '\n', 1000000)
1 loops, best of 3: 774 ms per loop

好多了！显然，findnth()的问题在于它被强制在split()期间复制字符串，这已经是在s = mm [:]之后第二次复制1.3 GB的数据。这就是find_nth()的第二个优点：我们可以直接在mm上使用它，因此不需要复制文件的任何副本：

In [7]: %timeit find_nth.find_nth(mm, '\n', 1000000)
1 loops, best of 3: 1.21 s per loop

看起来在操作 mm 与 s 时，存在一些小的性能损失，但这表明相对于 findnth 的总计 47 秒，find_nth() 能够在 1.2 秒内回答出问题。

在我的测试中，基于 str.find() 的方法并没有比基于 str.split() 的方法显著更差。因此，我认为应该接受 @tgamblin 或 @Mark Byers 的答案而不是 @bobince 的答案。

在我的测试中，上述版本的 find_nth() 是我能想到的最快的纯 Python 解决方案（与 @Mark Byers 的版本非常相似）。让我们看看使用 C 扩展模块能够做到多么好。下面是 _find_nthmodule.c:

#include <Python.h>
#include <string.h>

off_t _find_nth(const char *buf, size_t l, char c, int n) {
    off_t i;
    for (i = 0; i < l; ++i) {
        if (buf[i] == c && n-- == 0) {
            return i;
        }
    }
    return -1;
}

off_t _find_nth2(const char *buf, size_t l, char c, int n) {
    const char *b = buf - 1;
    do {
        b = memchr(b + 1, c, l);
        if (!b) return -1;
    } while (n--);
    return b - buf;
}

/* mmap_object is private in mmapmodule.c - replicate beginning here */
typedef struct {
    PyObject_HEAD
    char *data;
    size_t size;
} mmap_object;

typedef struct {
    const char *s;
    size_t l;
    char c;
    int n;
} params;

int parse_args(PyObject *args, params *P) {
    PyObject *obj;
    const char *x;

    if (!PyArg_ParseTuple(args, "Osi", &obj, &x, &P->n)) {
        return 1;
    }
    PyTypeObject *type = Py_TYPE(obj);

    if (type == &PyString_Type) {
        P->s = PyString_AS_STRING(obj);
        P->l = PyString_GET_SIZE(obj);
    } else if (!strcmp(type->tp_name, "mmap.mmap")) {
        mmap_object *m_obj = (mmap_object*) obj;
        P->s = m_obj->data;
        P->l = m_obj->size;
    } else {
        PyErr_SetString(PyExc_TypeError, "Cannot obtain char * from argument 0");
        return 1;
    }
    P->c = x[0];
    return 0;
}

static PyObject* py_find_nth(PyObject *self, PyObject *args) {
    params P;
    if (!parse_args(args, &P)) {
        return Py_BuildValue("i", _find_nth(P.s, P.l, P.c, P.n));
    } else {
        return NULL;    
    }
}

static PyObject* py_find_nth2(PyObject *self, PyObject *args) {
    params P;
    if (!parse_args(args, &P)) {
        return Py_BuildValue("i", _find_nth2(P.s, P.l, P.c, P.n));
    } else {
        return NULL;    
    }
}

static PyMethodDef methods[] = {
    {"find_nth", py_find_nth, METH_VARARGS, ""},
    {"find_nth2", py_find_nth2, METH_VARARGS, ""},
    {0}
};

PyMODINIT_FUNC init_find_nth(void) {
    Py_InitModule("_find_nth", methods);
}

这是 setup.py 文件：

from distutils.core import setup, Extension
module = Extension('_find_nth', sources=['_find_nthmodule.c'])
setup(ext_modules=[module])

使用python setup.py install正常安装即可。由于C代码只能查找单个字符，因此在此处具有优势，但让我们看看速度如何：

In [8]: %timeit _find_nth.find_nth(mm, '\n', 1000000)
1 loops, best of 3: 218 ms per loop

In [9]: %timeit _find_nth.find_nth(s, '\n', 1000000)
1 loops, best of 3: 216 ms per loop

In [10]: %timeit _find_nth.find_nth2(mm, '\n', 1000000)
1 loops, best of 3: 307 ms per loop

In [11]: %timeit _find_nth.find_nth2(s, '\n', 1000000)
1 loops, best of 3: 304 ms per loop

显然，速度要快得多。有趣的是，在内存和mmapped情况下，C级别之间没有区别。有趣的是看到基于string.h的memchr()库函数的_find_nth2()输给了以_find_nth()为基础的直接实现：memchr()中的额外“优化”显然适得其反...

总之，findnth()中的实现（基于str.split()）真的是一个糟糕的想法，因为(a)由于需要复制，它对于更大的字符串表现非常差，而且(b)它根本不适用于mmap.mmap对象。find_nth()中的实现（基于str.find()）应该在所有情况下优先考虑（因此成为这个问题的被接受答案）。

仍有很大的改进空间，因为C扩展运行几乎比纯Python代码快了将近4倍，这表明可能存在专用的Python库函数的情况。

- Stefan

Answer 6

最简单的方法？

text = "This is a test from a test ok" 

firstTest = text.find('test')

print text.find('test', firstTest + 1)

- forbzie

---

我可以想象，与其他解决方案相比，这也是非常高效的。 - Rotareti

那是最简单的方法，我喜欢它。 - sergiu.cs

Answer 7

我会采用find函数并带上索引参数，像这样实现此操作：

def find_nth(s, x, n):
    i = -1
    for _ in range(n):
        i = s.find(x, i + len(x))
        if i == -1:
            break
    return i

print find_nth('bananabanana', 'an', 3)

我猜这不是特别符合Pythonic的风格，但它很简单。你也可以使用递归来完成：

def find_nth(s, x, n, i = 0):
    i = s.find(x, i)
    if n == 1 or i == -1:
        return i 
    else:
        return find_nth(s, x, n - 1, i + len(x))

print find_nth('bananabanana', 'an', 3)

这是一种解决问题的有效方法，但我不知道是否更符合Pythonic风格。

- Mark Byers

---

可以使用for _ in xrange(n):代替while n: ... n-=1。 - jfs

@J.F. Sebastian：是的，我想那样更符合Python的风格。我会更新的。 - Mark Byers

顺便提一下：在Python 3中不再需要xrange了：http://diveintopython3.org/porting-code-to-python-3-with-2to3.html#xrange - Mark Byers

return find_nth(s, x, n - 1, i + 1) 应该改为 return find_nth(s, x, n - 1, i + len(x))。虽然不是很重要，但可以节省一些计算时间。 - dwlz

@dlo: 实际上在某些情况下这可能会给出不同的结果：find_nth('aaaa','aa',2)。我的代码返回1，你的返回2。 我猜你的实际上是发布者想要的。 我会更新我的代码。感谢评论。 - Mark Byers

打印 print find_nth('bananabanana', 'ban', 1) 对于迭代解决方案输出6而不是0，递归解决方案可以正常工作。要修复此问题，请在开头添加 if n == 0: return -1; i = -len(x)。 - JBallin

Answer 8

这将为您提供一个起始索引的数组，用于匹配您的字符串：yourstring。

import re
indices = [s.start() for s in re.finditer(':', yourstring)]

然后你的第n个条目将是：

n = 2
nth_entry = indices[n-1]

当然，你需要小心处理索引边界。你可以通过以下方式获取yourstring的实例数量：

num_instances = len(indices)

- modle13

Answer 9

如果您要查找某个字符（即长度为1的子字符串）的第n个出现次数，则以下函数可以通过构建给定字符出现位置的列表来实现：

def find_char_nth(string, char, n):
    """Find the n'th occurence of a character within a string."""
    return [i for i, c in enumerate(string) if c == char][n-1]

如果给定的字符少于 n 次出现，则会出现 IndexError: list index out of range。

这是从 @Zv_oDD 的 答案中演绎而来，针对单个字符情况进行了简化。

- coldfix

---

这很美。 - Hafiz Hilman Mohammad Sofian

Answer 10

这里有另一种使用re.finditer的方法。
不同之处在于，它只会在需要时查看“大堆干草”。

from re import finditer
from itertools import dropwhile
needle='an'
haystack='bananabanana'
n=2
next(dropwhile(lambda x: x[0]<n, enumerate(re.finditer(needle,haystack))))[1].start() 

- John La Rooy