查找字符串中第 n 次出现的子字符串
- 2025-02-07 08:44:00
- admin 原创
- 60
问题描述：
这看起来应该很简单，但是我是 Python 新手，想以最 Python 的方式去做。
我想找到字符串中第 n 次出现子字符串对应的索引。
一定有与我想要做的事情等同的事情
mystring.find("substring", 2nd)
如何在 Python 中实现这一点？
解决方案 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不是len(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中的几条规则：
简单比复杂更好。
平面比嵌套更好。
可读性很重要。
解决方案 2：
我认为马克的迭代方法是常用的方法。
这是使用字符串拆分的替代方法，它通常对于查找相关过程很有用：
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')
解决方案 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)
解决方案 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
解决方案 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, '
', 1000000)
1 loops, best of 3: 29.9 s per loop
显然表现很糟糕。让我们看看基于的方法如何str.find()：
In [6]: %timeit find_nth.find_nth(s, '
', 1000000)
1 loops, best of 3: 774 ms per loop
好多了！显然，findnth()的问题在于它在 期间被强制复制字符串split()，这已经是我们在 之后第二次复制 1.3 GB 的数据了s = mm[:]。 的第二个优点就在这里find_nth()：我们可以直接在 上使用它mm，这样就不需要复制文件了：
In [7]: %timeit find_nth.find_nth(mm, '
', 1000000)
1 loops, best of 3: 1.21 s per loop
mm与相比，似乎存在轻微的性能损失s，但这说明find_nth()可以在 1.2 秒内让我们得到答案，而findnth总共需要 47 秒。
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, '
', 1000000)
1 loops, best of 3: 218 ms per loop
In [9]: %timeit _find_nth.find_nth(s, '
', 1000000)
1 loops, best of 3: 216 ms per loop
In [10]: %timeit _find_nth.find_nth2(mm, '
', 1000000)
1 loops, best of 3: 307 ms per loop
In [11]: %timeit _find_nth.find_nth2(s, '
', 1000000)
1 loops, best of 3: 304 ms per loop
显然还是快了不少。有趣的是，在 C 级别上，内存和 mmapped 情况之间没有区别。同样有趣的是_find_nth2()，基于string.h的memchr()库函数的 输给了 中的直接实现_find_nth()： 中的额外“优化”memchr()显然适得其反……
总之，findnth()（基于str.split()）中的实现确实是一个坏主意，因为 (a) 由于需要复制，它在处理较大的字符串时性能很差，并且 (b) 它根本不能用于对象。 在所有情况下，都应该优先考虑（基于）mmap.mmap中的实现（因此是这个问题的可接受答案）。find_nth()`str.find()`
还有相当大的改进空间，因为 C 扩展的运行速度比纯 Python 代码快近 4 倍，这表明可能需要专用的 Python 库函数。
解决方案 6：
最简单的方法？
text = "This is a test from a test ok"
firstTest = text.find('test')
print text.find('test', firstTest + 1)
解决方案 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)
这是一种解决问题的实用方法，但我不知道这是否会使它更符合 Python 风格。
解决方案 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)
解决方案 9：
基于modele13的答案，但没有re模块依赖性。
def iter_find(haystack, needle):
return [i for i in range(0, len(haystack)) if haystack[i:].startswith(needle)]
我有点希望这是一个内置的字符串方法。
>>> iter_find("http://stackoverflow.com/questions/1883980/", '/')
[5, 6, 24, 34, 42]
解决方案 10：
这是使用 re.finditer 的另一种方法。
不同之处在于，它只会在必要时查看 haystack
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()
解决方案 11：
对于搜索字符第 n 次出现（即长度为 1 的子字符串）的特殊情况，以下函数通过构建给定字符出现的所有位置的列表来工作：
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 的答案中衍生出来的，并且针对单个字符的情况进行了简化。
解决方案 12：
这是另一个re+itertools版本，在搜索 astr或 a时应该可以工作RegexpObject。我承认，这可能设计得过于复杂，但出于某种原因，它让我很开心。
import itertools
import re
def find_nth(haystack, needle, n = 1):
"""
Find the starting index of the nth occurrence of ``needle`` in \n ``haystack``.
If ``needle`` is a ``str``, this will perform an exact substring
match; if it is a ``RegexpObject``, this will perform a regex
search.
If ``needle`` doesn't appear in ``haystack``, return ``-1``. If
``needle`` doesn't appear in ``haystack`` ``n`` times,
return ``-1``.
Arguments
---------
* ``needle`` the substring (or a ``RegexpObject``) to find
* ``haystack`` is a ``str``
* an ``int`` indicating which occurrence to find; defaults to ``1``
>>> find_nth("foo", "o", 1)
1
>>> find_nth("foo", "o", 2)
2
>>> find_nth("foo", "o", 3)
-1
>>> find_nth("foo", "b")
-1
>>> import re
>>> either_o = re.compile("[oO]")
>>> find_nth("foo", either_o, 1)
1
>>> find_nth("FOO", either_o, 1)
1
"""
if (hasattr(needle, 'finditer')):
matches = needle.finditer(haystack)
else:
matches = re.finditer(re.escape(needle), haystack)
start_here = itertools.dropwhile(lambda x: x[0] < n, enumerate(matches, 1))
try:
return next(start_here)[1].start()
except StopIteration:
return -1
解决方案 13：
提供另一个“棘手”的解决方案，即使用split和join。
在您的示例中，我们可以使用
len("substring".join([s for s in ori.split("substring")[:2]]))
解决方案 14：
>>> s="abcdefabcdefababcdef"
>>> j=0
>>> for n,i in enumerate(s):
... if s[n:n+2] =="ab":
... print n,i
... j=j+1
... if j==2: print "2nd occurence at index position: ",n
...
0 a
6 a
2nd occurence at index position: 6
12 a
14 a
解决方案 15：
# return -1 if nth substr (0-indexed) d.n.e, else return index
def find_nth(s, substr, n):
i = 0
while n >= 0:
n -= 1
i = s.find(substr, i + 1)
return i
解决方案 16：
不使用循环和递归的解决方案。
在编译方法中使用所需的模式，并在变量“n”中输入所需的出现次数，最后一条语句将打印给定字符串中模式第 n 次出现的起始索引。这里 finditer 的结果即迭代器被转换为列表并直接访问第 n 个索引。
import re
n=2
sampleString="this is history"
pattern=re.compile("is")
matches=pattern.finditer(sampleString)
print(list(matches)[n].span()[0])
解决方案 17：
这是我在字符串中查找n出现次数的解决方案：b`a`
from functools import reduce
def findNth(a, b, n):
return reduce(lambda x, y: -1 if y > x + 1 else a.find(b, x + 1), range(n), -1)
它是纯 Python 的，并且是迭代的。对于 0 或n太大，它返回 -1。它是一行代码，可以直接使用。以下是一个例子：
>>> reduce(lambda x, y: -1 if y > x + 1 else 'bibarbobaobaotang'.find('b', x + 1), range(4), -1)
7
解决方案 18：
我使用了 findnth() 函数并遇到了一些问题，因此我重写了该函数的更快版本（没有列表拆分）：
def findnth(haystack, needle, n):
if not needle in haystack or haystack.count(needle) < n:
return -1
last_index = 0
cumulative_last_index = 0
for i in range(0, n):
last_index = haystack[cumulative_last_index:].find(needle)
cumulative_last_index += last_index
# if not last element, then jump over it
if i < n-1:
cumulative_last_index += len(needle)
return cumulative_last_index
解决方案 19：
替换一行代码很棒，但只有在 XX 和 bar 长度相同的情况下才有效
一个好的、通用的定义是：
def findN(s,sub,N,replaceString="XXX"):
return s.replace(sub,replaceString,N-1).find(sub) - (len(replaceString)-len(sub))*(N-1)
解决方案 20：
定义：
def get_first_N_words(mytext, mylen = 3):
mylist = list(mytext.split())
if len(mylist)>=mylen: return ' '.join(mylist[:mylen])
使用方法：
get_first_N_words(' One Two Three Four ' , 3)
输出：
'One Two Three'
解决方案 21：
当提供的输入发生值高于实际发生次数时，避免失败或输出不正确。例如，在字符串“溢出”中，如果您检查“o”的第 3 次出现（它只有 2 次出现），则下面的代码将返回警告或消息，表明发生值已超出。
输入的输入事件已超过实际发生次数。
def check_nth_occurrence (string, substr, n):
## Count the Occurrence of a substr
cnt = 0
for i in string:
if i ==substr:
cnt = cnt + 1
else:
pass
## Check if the Occurrence input has exceeded the actual count of Occurrence
if n > cnt:
print (f' Input Occurrence entered has exceeded the actual count of Occurrence')
return
## Get the Index value for first Occurrence of the substr
index = string.find(substr)
## Get the Index value for nth Occurrence of Index
while index >= 0 and n > 1:
index = string.find(substr, index+ 1)
n -= 1
return index
解决方案 22：
以防万一有人想从后面找到第 n 个：
def find_nth_reverse(haystack: str, needle: str, n: int) -> int:
end = haystack.rfind(needle)
while end >= 0 and n > 1:
end = haystack.rfind(needle, 0, end - len(needle))
n -= 1
return end
解决方案 23：
这是一个简单而有趣的方法：
def index_of_nth(text, substring, n) -> int:
index = 0
for _ in range(n):
index = text.index(substring, index) + 1
return index - 1
解决方案 24：
我是这样解决的。
def second_index(text: str, symbol: str) -> [int, None]:
"""
returns the second index of a symbol in a given text
"""
first = text.find(symbol)
result = text.find(symbol,first+1)
if result > 0: return result
解决方案 25：
虽然 Sriram Murali 使用递归给出的答案很棒，但使用理解的另一种快速而粗糙的选项可能如下所示：
def FindNthOccurrence(main:str, sub:str, n:int = 0) -> int:
return [idx for idx, val in enumerate(main) if main[idx:idx+len(sub)]==sub][n]
注意：此解决方案假定您可以切实地枚举整个“主”字符串。
解决方案 26：
这才是你真正想要的答案：
def Find(String,ToFind,Occurence = 1):
index = 0
count = 0
while index <= len(String):
try:
if String[index:index + len(ToFind)] == ToFind:
count += 1
if count == Occurence:
return index
break
index += 1
except IndexError:
return False
break
return False
解决方案 27：
对于具有基本编程知识的人来说，这是一个简单的解决方案：
# Function to find the nth occurrence of a substring in a text
def findnth(text, substring, n):
# variable to store current index in loop
count = -1
# n count
occurance = 0
# loop through string
for letter in text:
# increment count
count += 1
# if current letter in loop matches substring target
if letter == substring:
# increment occurance
occurance += 1
# if this is the nth time the substring is found
if occurance == n:
# return its index
return count
# otherwise indicate there is no match
return "No match"
# example of how to call function
print(findnth('C$100$150xx', "$", 2))
解决方案 28：
怎么样：
c = os.getcwd().split('\\')
print '\\'.join(c[0:-2])
