문자열에서 하위 문자열의 n번째 발생 찾기

문자열에서 하위 문자열의 n번째 발생 찾기

이것은 꽤 사소한 것처럼 보이지만, 저는 파이썬에 익숙하지 않고 가장 파이썬적인 방식으로 하고 싶습니다.

문자열 내 하위 문자열의 n번째 발생에 해당하는 인덱스를 찾고 싶습니다.

내가 하고 싶은 것과 동등한 것이 있어야 합니다.

mystring.find("substring", 2nd)

Python에서 어떻게 이를 달성할 수 있습니까?

간단한 반복 솔루션의 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

이것은 Mark 버전보다 읽기 쉬우며 분할 버전이나 정규식 가져오기 모듈의 추가 메모리가 필요하지 않습니다.그것은 또한 다양한 것과 달리 파이썬의 젠에 있는 몇 가지 규칙을 고수합니다.re접근 방식:

1. 단순한 것이 복잡한 것보다 낫습니다.
2. 내포된 것보다 평평한 것이 좋습니다.
3. 가독성이 중요합니다.

저는 마크의 반복적인 접근이 일반적인 방법이라고 생각합니다.

다음은 문자열 분할과 관련된 프로세스를 찾는 데 유용할 수 있는 대안입니다.

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

문자열에서 하위 문자열이 두 번째로 나타납니다.

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

된 가장 @bobince의 @bobince의 @bobince의 @bobince의 @bobince의 @bobince를 비교한 벤치마킹 결과를 제시합니다.findnth()))str.split() 또는 Byers's) vs. @tgamblin's @Mark Byers's.find_nth()))str.find()C 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.3GB 파일에서 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 » 4GB »를 해 보겠습니다. 벤치마크해 보겠습니다.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에 이어 두 입니다.GB의 데이터를 복사한 후 두 번째입니다.s = mm[:]▁of 두 번째 장점이 있습니다.find_nth()우리는 그것을 사용할 수 있습니다.mm파일의 복사본이 0개 필요하도록 직접 설정할 수 있습니다.

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

에 약간의 성능 저하가 발생한 것 같습니다.mm대 대s하지만 이것은 그것을 보여줍니다.find_nth() 수 .findnth47파운드입니다.

저는 어떤 경우도 발견하지 못했습니다str.find()기반 접근 방식은 훨씬 더 나빴습니다.str.split()따라서 이 시점에서 저는 @bobince의 대답 대신 @tgamblin의 대답이나 @Mark Byers의 대답을 받아들여야 한다고 주장합니다.

테스트한 로는, 제가테한바로는은, 의버전트의 입니다.find_nth()위는 제가 생각해 낼 수 있는 가장 빠른 순수 파이썬 솔루션이었습니다(@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 수준에 차이가 없습니다.그것을 보는 것 또한 흥미롭습니다._find_nth2()은 바를탕로으에 있습니다.string.h의memchr() 함수, 이브러기능리손대, 에 대해 패배합니다._find_nth()의추최인 "적화는 "의 인 "memchr()보아하니 역효과를 내고 있는 것 같군요...

결적으로은, 구현의론의 findnth()))str.split()(a) 필요한 복사로 인해 더 큰 문자열에 대해 끔찍하게 수행되고 (b) 작동하지 않기 때문에 정말 나쁜 생각입니다.mmap.mmap물건이 전혀 없습니다.의 find_nth()))str.find())는 모든 상황에서 선호되어야 합니다(따라서 이 질문에 대한 허용된 답변입니다).

C 확장이 순수 파이썬 코드보다 거의 4배 더 빠르게 실행되어 전용 파이썬 라이브러리 함수에 대한 사례가 있을 수 있기 때문에 아직 개선의 여지가 꽤 있습니다.

가장 간단한 방법은?

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)

제 생각에는 특별히 파이썬적인 것은 아니지만, 간단합니다.대신 재귀를 사용할 수 있습니다.

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)

그것은 그것을 해결하는 기능적인 방법이지만, 저는 그것이 그것을 더 파이썬적으로 만드는지 모르겠습니다.

일치 항목에 대한 시작 인덱스 배열을 제공합니다.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)

문자의 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의 답변에서 파생되었으며 단일 문자의 경우 단순화되었습니다.

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

모델13의 답변을 기반으로 구축하지만, 그것 없이.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]

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

"한션른제"를 사용하는 또 split그리고.join.

당신의 예에서, 우리는 다음을 사용할 수 있습니다.

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

루프와 재귀를 사용하지 않는 솔루션.

컴파일 방법에서 필요한 패턴을 사용하고 변수 '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 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)

이것은 순수한 파이썬이고 반복적입니다. 또는 0의 는n너무 크면 -1을 반환합니다.이것은 원라이너이며 직접 사용할 수 있습니다.다음은 예입니다.

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

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

교체 라이너 하나는 좋지만 XX와 바의 렌지가 동일하기 때문에 작동합니다.

적절하고 일반적인 정의는 다음과 같습니다.

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

정의:

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'

제공된 발생에 대한 입력 값이 실제 발생 횟수보다 높을 경우 오류가 발생하거나 잘못된 출력을 방지합니다.예를 들어 'overflow' 문자열에서 'o'가 세 번째로 발생하는지 확인할 경우(발생 횟수가 두 번만 발생함), 아래 코드는 발생 값을 초과했음을 나타내는 경고 또는 메시지를 반환합니다.

입력한 발생 입력이 실제 발생 횟수를 초과했습니다.

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

이렇게 풀었어요.

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 

이것이 당신이 진정으로 원하는 답입니다.

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

기본적인 프로그래밍 지식을 갖춘 사용자를 위한 간단한 솔루션:

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

어때요?

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

언급URL : https://stackoverflow.com/questions/1883980/find-the-nth-occurrence-of-substring-in-a-string