Trouver la nième occurrence de substring dans une chaîne

Voici une version plus pythonique de la solution itérative simple:

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

exemple:

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

Si vous voulez trouver le n-ième chevauchement occurrence de needle , vous pouvez incrémenter par 1 au lieu de len(needle) , comme ceci:

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

exemple:

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

C'est plus facile à lire que la version de Mark, et il ne nécessite pas la mémoire supplémentaire de la version de fractionnement ou d'importation de module d'expression régulière. Il adhère également à quelques-unes des règles dans le Zen de python , contrairement aux diverses re approches:

1. Simple vaut mieux que complexe.
2. plat est mieux que niché.
3. la lisibilité compte.

cela va trouver la deuxième occurrence de la chaîne de chaîne.

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

Edit: Je n'ai pas beaucoup pensé à la performance, mais une rapide récursion peut aider à trouver la nième occurrence:

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)

sachant que regex n'est pas toujours la meilleure solution, j'en utiliserais probablement une ici:

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

j'offre quelques résultats de benchmarking comparant les approches les plus importantes présentées jusqu'à présent, à savoir findnth() de @bobince (basé sur str.split() ) vs. find_nth() de @tgamblin ou str.find() de @Mark Byers (basé sur str.find() ). Je vais aussi comparer avec une extension C ( _find_nth.so ) pour voir à quelle vitesse nous pouvons aller. Voici 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

bien sûr, la performance importe le plus si la chaîne est grande, donc supposons que nous voulons trouver le 1000001st newline ('\n') Dans un fichier de 1.3 Go appelé'bigfile'. Pour sauver la mémoire, nous aimerions travailler sur une mmap.mmap représentation d'objet du fichier:

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)

il y a déjà le premier problème avec findnth() , depuis mmap.mmap les objets ne supportent pas split() . Nous devons donc copier l'ensemble du fichier dans la mémoire:

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

Aïe! Heureusement s tient toujours dans les 4 Go de mémoire de mon Macbook Air, donc indice de référence findnth() :

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

c'est clairement une terrible performance. Voyons comment l'approche basée sur str.find() fait:

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

beaucoup mieux! Clairement, findnth() ' s problème est qu'il est forcé de copier la chaîne pendant split() , qui est déjà la deuxième fois que nous avons copié les 1,3 Go de données autour après s = mm[:] . Voici le deuxième avantage de find_nth() : nous pouvons l'utiliser sur mm directement, de sorte que zéro copies du fichier sont nécessaires:

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

il semble y avoir une petite pénalité d'exécution sur mm vs. s , mais ceci illustre que find_nth() peut nous obtenir une réponse en 1.2 s comparé à findnth total de 47 S.

Je n'ai trouvé aucun cas où l'approche basée sur str.find() était nettement pire que l'approche basée sur str.split() , donc à ce point, Je dirais que la réponse de @tgamblin ou de @Mark Byers devrait être acceptée au lieu de celle de @bobince.

dans mes tests, la version de find_nth() ci-dessus était la solution Python pure la plus rapide que j'ai pu trouver (très similaire à la version de @Mark Byers). Voyons ce que nous pouvons faire de mieux avec un module d'extension C. Voici _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);
}

voici le fichier setup.py :

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

Installer comme d'habitude avec python setup.py install . Le code C joue un avantage ici puisqu'il est limité à la recherche de caractères simples, mais voyons à quelle vitesse c'est:

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

Clairement un peu plus rapide encore. Fait intéressant, il n'y a pas de différence au niveau C entre les cas en mémoire et les cas cartographiés. Il est également intéressant de voir que _find_nth2() , qui est basé sur string.h de l ' memchr() fonction de bibliothèque, perd contre la mise en œuvre simple en _find_nth() : les" optimisations "supplémentaires dans memchr() semblent se retourner contre elles...

en conclusion, la mise en œuvre dans findnth() (basé sur str.split() ) est vraiment une mauvaise idée, puisque (A) il se produit terriblement pour les cordes plus grandes en raison de la copie requise, et (b) cela ne fonctionne pas du tout sur les objets mmap.mmap . La mise en œuvre dans find_nth() (basé sur str.find() ) doit être préférée dans toutes les circonstances (et donc être accepté la réponse à cette question).

il y a encore pas mal de place à l'amélioration, puisque L'extension C courait presque un facteur de 4 plus vite que le code Python pur, indiquant qu'il pourrait y avoir un cas pour une fonction de bibliothèque Python dédiée.

je ferais probablement quelque chose comme ça, en utilisant la fonction find qui prend un paramètre d'index:

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)

ce n'est pas particulièrement pythonique je suppose, mais c'est simple. Vous pouvez le faire en utilisant la récursion à la place:

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)

c'est une façon fonctionnelle de le résoudre, mais je ne sais pas si cela le rend plus pythonique.

la manière la plus simple?

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

firstTest = text.find('test')

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

Voici une autre version re + itertools qui devrait fonctionner lors de la recherche d'un str ou d'un RegexpObject . Je reconnais volontiers que c'est probablement conçu, mais pour quelque raison il me divertir.

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

Voici une autre approche utilisant re.finditer.

La différence est que cela ne regarde dans la meule de foin autant que nécessaire

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

cela vous donnera un tableau des indices de départ pour les correspondances à yourstring :

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

alors votre nième entrée serait:

n = 2
nth_entry = indices[n-1]

bien sûr, vous devez être prudent avec l'indice de limites. Vous pouvez obtenir le nombre d'occurrences de yourstring comme ceci:

num_instances = len(indices)

S'appuie sur modle13 's answer, mais sans la dépendance du module re .

def iter_find(haystack, needle):
    return [i for i in range(0, len(haystack)) if haystack[i:].startswith(needle)]

j'aimerais que ce soit une méthode de chaîne intégrée.

>>> iter_find("/q/find-the-nth-occurrence-of-substring-in-a-string-23648/", '/')
[5, 6, 24, 34, 42]

le remplacer une doublure est grand, mais ne fonctionne que parce que XX et barre ont le même lentgh

un bon et général def serait:

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

fournissant une autre solution" délicate", qui utilisent split et join .

dans votre exemple, nous pouvons utiliser

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

Que Diriez-vous de:

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

C'est la réponse que vous voulez vraiment:

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

# 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