Rechercher la nième occurrence de sous-chaîne dans une chaîne

Cela semble être assez trivial, mais je suis nouveau en Python et je veux le faire de la manière la plus pythonique.

Je veux trouver l'index correspondant à la nième occurrence d'une sous-chaîne dans une chaîne.

Il doit y avoir quelque chose d'équivalent à ce que JE VEUX faire, c'est-à-dire

mystring.find("substring", 2nd)

Comment pouvez-vous y parvenir en Python?

L'approche itérative de Mark serait la manière habituelle, je pense.

Voici une alternative avec le fractionnement de chaînes, qui peut souvent être utile pour rechercher des processus liés:

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)

Et voici un one-liner rapide (et un peu sale, en ce sens que vous devez choisir une balle qui ne peut pas correspondre à l'aiguille):

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

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 la nième occurrence de chevauchement de needle, vous pouvez incrémenter de 1au 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

Ceci est plus facile à lire que la version de Mark et ne nécessite pas la mémoire supplémentaire de la version de fractionnement ou l'importation du module d'expression régulière. Il adhère également à quelques-unes des règles du Zen de python , contrairement aux différentes reapproches:

1. Le simple vaut mieux que le complexe.
2. Flat est mieux que niché.
3. La lisibilité compte.

Cela trouvera la deuxième occurrence de sous-chaîne dans la chaîne.

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

Edit: Je n'ai pas beaucoup réfléchi aux performances, mais une récursivité rapide 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)

Comprendre que l'expression régulière 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

Je propose des résultats d'analyse comparative comparant les approches les plus importantes présentées jusqu'à présent, à savoir @ bobince findnth()(basé sur str.split()) vs @ tgamblin's ou @Mark Byers find_nth()(basé sur str.find()). Je vais également 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, les performances sont plus importantes si la chaîne est volumineuse, alors supposons que nous souhaitons trouver la 1000001e nouvelle ligne ('\ n') dans un fichier de 1,3 Go appelé 'bigfile'. Pour économiser de la mémoire, nous aimerions travailler sur une mmap.mmapreprésentation 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(), puisque les mmap.mmapobjets ne prennent pas en charge split(). Nous devons donc copier tout le fichier en 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

Aie! Heureusement, stient toujours dans les 4 Go de mémoire de mon Macbook Air, alors comparons-nous findnth():

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

Clairement une performance terrible. 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

Bien mieux! De toute évidence, findnth()le problème est qu'il est obligé de copier la chaîne pendant split(), ce qui est déjà la deuxième fois que nous copions les 1,3 Go de données après s = mm[:]. Voici le deuxième avantage de find_nth(): Nous pouvons l'utiliser mmdirectement, de sorte qu'aucune copie du fichier ne soit requise:

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é de performance opérant sur mmvs. s, mais cela montre que cela find_nth()peut nous donner une réponse en 1,2 s par rapport au findnthtotal de 47 s.

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

Lors de mes tests, la version find_nth()ci - dessus était la solution pure Python la plus rapide que je pouvais proposer (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 setup.pyfichier:

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

Installez comme d'habitude avec python setup.py install. Le code C joue ici un avantage puisqu'il se limite à trouver des caractères uniques, mais voyons à quelle vitesse cela 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 encore un peu plus rapide. Fait intéressant, il n'y a aucune différence au niveau C entre les cas en mémoire et mmappés. Il est également intéressant de voir que _find_nth2(), qui est basé sur string.hla memchr()fonction de bibliothèque de 's , perd contre la simple implémentation dans _find_nth(): Les "optimisations" supplémentaires dans memchr()sont apparemment contre-productives ...

En conclusion, l'implémentation dans findnth()(basée sur str.split()) est vraiment une mauvaise idée, car (a) elle fonctionne terriblement pour des chaînes plus grandes en raison de la copie requise, et (b) elle ne fonctionne pas du tout sur les mmap.mmapobjets. La mise en œuvre dans find_nth()(basée sur str.find()) doit être préférée en toutes circonstances (et donc être la réponse acceptée à cette question).

Il reste encore beaucoup à faire, car l'extension C a fonctionné presque 4 fois plus vite que le code Python pur, ce qui indique qu'il pourrait y avoir un cas pour une fonction de bibliothèque Python dédiée.

Le moyen le plus simple?

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

firstTest = text.find('test')

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

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écursivité à 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 un moyen fonctionnel de le résoudre, mais je ne sais pas si cela le rend plus pythonique.

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 les limites d'index. Vous pouvez obtenir le nombre d'instances yourstringcomme ceci:

num_instances = len(indices)

Voici une autre approche utilisant re.finditer.
La différence est que cela ne regarde dans la botte de foin que dans la mesure où cela est 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() 

Voici une autre version re+ itertoolsqui devrait fonctionner lors de la recherche de a strou a RegexpObject. J'admettrai librement que cela est probablement sur-conçu, mais pour une raison quelconque, cela m'a amusé.

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

Construire sur la réponse de modle13 , mais sans la redépendance du module.

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

Je souhaite un peu que ce soit une méthode de chaîne intégrée.

>>> iter_find("http://stackoverflow.com/questions/1883980/", '/')
[5, 6, 24, 34, 42]

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

Fournir une autre solution "délicate", qui utilise splitet join.

Dans votre exemple, nous pouvons utiliser

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

# 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

Solution sans utiliser de boucles ni de récursivité.

Utilisez le modèle requis dans la méthode de compilation et entrez l'occurrence souhaitée dans la variable 'n' et la dernière instruction imprimera l'index de départ de la nième occurrence du modèle dans la chaîne donnée. Ici, le résultat de finditer ie iterator est converti en liste et accède directement au nième index.

import re
n=2
sampleString="this is history"
pattern=re.compile("is")
matches=pattern.finditer(sampleString)
print(list(matches)[n].span()[0])

Pour le cas particulier où vous recherchez la nième occurrence d'un caractère (c'est-à-dire une sous-chaîne de longueur 1), la fonction suivante fonctionne en construisant une liste de toutes les positions d'occurrences du caractère donné:

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]

S'il y a moins d' noccurrences du caractère donné, cela donnera IndexError: list index out of range.

Ceci est dérivé de la réponse de @ Zv_oDD et simplifié pour le cas d'un seul caractère.

La doublure de remplacement est excellente mais ne fonctionne que parce que XX et la barre ont la même longueur

Une bonne définition générale serait:

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

Voici 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

Voici ma solution pour trouver l' noccurrance de bin string 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)

C'est du Python pur et itératif. Pour 0 ou nqui est trop grand, il renvoie -1. C'est une doublure et peut être utilisé directement. Voici un exemple:

>>> reduce(lambda x, y: -1 if y > x + 1 else 'bibarbobaobaotang'.find('b', x + 1), range(4), -1)
7

Def:

def get_first_N_words(mytext, mylen = 3):
    mylist = list(mytext.split())
    if len(mylist)>=mylen: return ' '.join(mylist[:mylen])

Utiliser:

get_first_N_words('  One Two Three Four ' , 3)

Production:

'One Two Three'

Que diriez-vous:

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