Найти 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

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

1. Простое лучше сложного.
2. Flat лучше, чем вложенный.
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)

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

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

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

Конечно, производительность имеет наибольшее значение, если строка большая, поэтому предположим, что мы хотим найти 1000001-й символ новой строки ('\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

Ой! К счастью, 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.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

Явно еще немного быстрее. Интересно, что на уровне 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.

Самый простой способ?

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

firstTest = text.find('test')

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

Я бы, вероятно, сделал что-то подобное, используя функцию поиска, которая принимает параметр индекса:

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.

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

Вот еще один подход с использованием 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() 

Вот еще одна версия 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

Основываясь на ответе modle13, но без зависимости от модуля 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]

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

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

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

Решение без использования циклов и рекурсии.

Используйте требуемый шаблон в методе компиляции и введите желаемое вхождение в переменную '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])

Для особого случая, когда вы ищете 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 и упрощено для случая одного символа.

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

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

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

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

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

Вот мое решение для поиска nth появления 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

Защита:

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'

Избегайте сбоя или неправильного вывода, когда предоставленное входное значение для вхождения превышает фактическое количество вхождений. Например, в строке «переполнение», если вы проверите 3-е вхождение «o» (у него есть только 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

На всякий случай, если кто-то захочет найти 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

Вот простой и интересный способ сделать это:

def index_of_nth(text, substring, n) -> int:
    index = 0
    for _ in range(n):
        index = text.index(substring, index) + 1
    return index - 1

Как насчет:

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