Найти n-е вхождение подстроки в строку

Я думаю, что итеративный подход Марка был бы обычным делом.

Вот альтернатива с разделением строк, которая часто может быть полезна для процессов, связанных с поиском:

 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') 

Вот более Pythonic версия простого итеративного решения:

 def find_nth(haystack, needle, n): 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 

Это легче читать, чем версия Марка, и она не требует дополнительной памяти для разделяющей версии или импорта модуля регулярных выражений. Он также придерживается некоторых правил в Zen python , в отличие от различных подходов:

1. Простой лучше, чем сложный.
2. Плоский лучше, чем вложенный.
3. Показатели удобочитаемости.

Понимание того, что регулярное выражение не всегда является лучшим решением, я бы, вероятно, использовал его здесь:

 >>> 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 

Это найдет второе вхождение подстроки в строке.

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

Я предлагаю некоторые результаты сравнительного анализа, сравнивающие наиболее известные подходы, представленные до сих пор, а именно: bbince's findnth() (на основе str.split() ) vs. @ tgamblin или @Mark Byers ' find_nth() (на основе str.find() ). Я также _find_nth.so с расширением 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 

Конечно, производительность важна, если строка большая, поэтому предположим, что мы хотим найти 1000001st новую строку ('\ n') в 1,3-Гбайт-файле под названием «bigfile». Чтобы сохранить память, мы хотели бы работать над представлением объекта 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 

Ой! К счастью, он все еще вписывается в 4 ГБ памяти моего Macbook Air, поэтому давайте 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() , которая уже второй раз скопировала 1,3 ГБ данных вокруг после s = mm[:] . Здесь второе преимущество 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 , но это иллюстрирует, что find_nth() может получить ответ в 1.2 с по сравнению с findnth общей сложности 47 с.

Я не обнаружил случаев, когда str.find() на основе str.find() был значительно хуже, чем str.split() на основе str.split() , поэтому на этом этапе я бы сказал, что ответ @ tgamblin или @Mark Byers должен быть принят вместо @ bobince's ,

В моем тестировании версия 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(Ps, Pl, Pc, Pn)); } 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(Ps, Pl, Pc, Pn)); } 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 

Ясно еще немного быстрее. Интересно, что нет разницы на уровне C между операциями in-memory и mmapped. Также интересно видеть, что _find_nth2() , основанный на библиотечной функции memchr() библиотеки string.h , проигрывает против простой реализации в _find_nth() : дополнительные «оптимизации» в memchr() , по-видимому, обходятся. ..

В заключение, реализация findnth() (основанная на str.split() ) на самом деле является плохой идеей, поскольку (а) она ужасно работает для больших строк из-за требуемого копирования, и (б) она не работает mmap.mmap вообще. Реализация в find_nth() (на основе str.find() ) должна быть предпочтительной при любых обстоятельствах (и, следовательно, быть принятым ответом на этот вопрос).

По-прежнему существует довольно много возможностей для улучшения, поскольку расширение C работает почти в 4 раза быстрее, чем чистый код Python, что указывает на то, что может быть случай для выделенной функции библиотеки Python.

Я бы, наверное, сделал что-то подобное, используя функцию 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.

Простейший путь?

 text = "This is a test from a test ok" firstTest = text.find('test') print text.find('test', firstTest + 1) 

Вот еще itertools версия re + itertools которая должна работать при поиске либо str либо RegexpObject . Я буду свободно признавать, что это, вероятно, чрезмерно спроектировано, но почему-то это развлекало меня.

 import itertools import re def find_nth(haystack, needle, n = 1): """ Find the starting index of the nth occurrence of ``needle`` in \ ``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 

Вот еще один подход, использующий 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() 

 >>> 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 

Это даст вам массив начальных индексов для совпадений с 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) 

Замена одного вкладыша велик, но работает только потому, что XX и бар имеют одинаковый размер

Хорошим и общим понятием будет:

 def findN(s,sub,N,replaceString="XXX"): return s.replace(sub,replaceString,N-1).find(sub) - (len(replaceString)-len(sub))*(N-1) 

Предоставление другого «сложного» решения, которое использует split и join .

В вашем примере мы можем использовать

 len("substring".join([s for s in ori.split("substring")[:2]])) 

Как насчет:

 c = os.getcwd().split('\\') print '\\'.join(c[0:-2]) 

Это ответ, который вы действительно хотите:

 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 

Основываясь на ответе modle13 , но без зависимости от модуля.

 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]