Как найти все вхождения символа в строке – Сайт, где вы сможете решить свои вопросы

There is no simple built-in string function that does what you’re looking for, but you could use the more powerful regular expressions:

import re
[m.start() for m in re.finditer('test', 'test test test test')]
#[0, 5, 10, 15]

If you want to find overlapping matches, lookahead will do that:

[m.start() for m in re.finditer('(?=tt)', 'ttt')]
#[0, 1]

If you want a reverse find-all without overlaps, you can combine positive and negative lookahead into an expression like this:

search = 'tt'
[m.start() for m in re.finditer('(?=%s)(?!.{1,%d}%s)' % (search, len(search)-1, search), 'ttt')]
#[1]

re.finditer returns a generator, so you could change the [] in the above to () to get a generator instead of a list which will be more efficient if you’re only iterating through the results once.

answered Jan 12, 2011 at 2:43

moinudinmoinudin

133k45 gold badges189 silver badges214 bronze badges

>>> help(str.find)
Help on method_descriptor:

find(...)
    S.find(sub [,start [,end]]) -> int

Thus, we can build it ourselves:

def find_all(a_str, sub):
    start = 0
    while True:
        start = a_str.find(sub, start)
        if start == -1: return
        yield start
        start += len(sub) # use start += 1 to find overlapping matches

list(find_all('spam spam spam spam', 'spam')) # [0, 5, 10, 15]

No temporary strings or regexes required.

answered Jan 12, 2011 at 3:13

Karl KnechtelKarl Knechtel

61.5k11 gold badges97 silver badges146 bronze badges

Here’s a (very inefficient) way to get all (i.e. even overlapping) matches:

>>> string = "test test test test"
>>> [i for i in range(len(string)) if string.startswith('test', i)]
[0, 5, 10, 15]

answered Jan 12, 2011 at 2:48

thkalathkala

83.4k23 gold badges155 silver badges199 bronze badges

Use re.finditer:

import re
sentence = input("Give me a sentence ")
word = input("What word would you like to find ")
for match in re.finditer(word, sentence):
    print (match.start(), match.end())

For word = "this" and sentence = "this is a sentence this this" this will yield the output:

(0, 4)
(19, 23)
(24, 28)

answered Feb 3, 2016 at 19:01

IdosIdos

15k14 gold badges59 silver badges73 bronze badges

Again, old thread, but here’s my solution using a generator and plain str.find.

def findall(p, s):
    '''Yields all the positions of
    the pattern p in the string s.'''
    i = s.find(p)
    while i != -1:
        yield i
        i = s.find(p, i+1)

Example

x = 'banananassantana'
[(i, x[i:i+2]) for i in findall('na', x)]

returns

[(2, 'na'), (4, 'na'), (6, 'na'), (14, 'na')]

answered Dec 23, 2015 at 23:09

AkiRossAkiRoss

11.6k6 gold badges59 silver badges85 bronze badges

You can use re.finditer() for non-overlapping matches.

>>> import re
>>> aString = 'this is a string where the substring "is" is repeated several times'
>>> print [(a.start(), a.end()) for a in list(re.finditer('is', aString))]
[(2, 4), (5, 7), (38, 40), (42, 44)]

but won’t work for:

In [1]: aString="ababa"

In [2]: print [(a.start(), a.end()) for a in list(re.finditer('aba', aString))]
Output: [(0, 3)]

AnukuL

5751 gold badge7 silver badges21 bronze badges

answered Jan 12, 2011 at 2:55

Chinmay KanchiChinmay Kanchi

62.1k22 gold badges86 silver badges114 bronze badges

Come, let us recurse together.

def locations_of_substring(string, substring):
    """Return a list of locations of a substring."""

    substring_length = len(substring)    
    def recurse(locations_found, start):
        location = string.find(substring, start)
        if location != -1:
            return recurse(locations_found + [location], location+substring_length)
        else:
            return locations_found

    return recurse([], 0)

print(locations_of_substring('this is a test for finding this and this', 'this'))
# prints [0, 27, 36]

No need for regular expressions this way.

answered Nov 1, 2013 at 3:16

Cody PiersallCody Piersall

8,2242 gold badges42 silver badges57 bronze badges

If you’re just looking for a single character, this would work:

string = "dooobiedoobiedoobie"
match = 'o'
reduce(lambda count, char: count + 1 if char == match else count, string, 0)
# produces 7

Also,

string = "test test test test"
match = "test"
len(string.split(match)) - 1
# produces 4

My hunch is that neither of these (especially #2) is terribly performant.

answered Sep 24, 2014 at 21:12

jstaabjstaab

3,30925 silver badges40 bronze badges

this is an old thread but i got interested and wanted to share my solution.

def find_all(a_string, sub):
    result = []
    k = 0
    while k < len(a_string):
        k = a_string.find(sub, k)
        if k == -1:
            return result
        else:
            result.append(k)
            k += 1 #change to k += len(sub) to not search overlapping results
    return result

It should return a list of positions where the substring was found.
Please comment if you see an error or room for improvment.

answered Apr 1, 2015 at 9:23

ThurinesThurines

1111 silver badge3 bronze badges

This does the trick for me using re.finditer

import re

text = 'This is sample text to test if this pythonic '
       'program can serve as an indexing platform for '
       'finding words in a paragraph. It can give '
       'values as to where the word is located with the '
       'different examples as stated'

#  find all occurances of the word 'as' in the above text

find_the_word = re.finditer('as', text)

for match in find_the_word:
    print('start {}, end {}, search string '{}''.
          format(match.start(), match.end(), match.group()))

answered Jul 6, 2018 at 9:34

Bruno VermeulenBruno Vermeulen

2,8732 gold badges14 silver badges28 bronze badges

This thread is a little old but this worked for me:

numberString = "onetwothreefourfivesixseveneightninefiveten"
testString = "five"

marker = 0
while marker < len(numberString):
    try:
        print(numberString.index("five",marker))
        marker = numberString.index("five", marker) + 1
    except ValueError:
        print("String not found")
        marker = len(numberString)

wingerse

3,6301 gold badge27 silver badges57 bronze badges

answered Sep 1, 2014 at 12:48

Andrew HAndrew H

46610 silver badges22 bronze badges

You can try :

>>> string = "test test test test"
>>> for index,value in enumerate(string):
    if string[index:index+(len("test"))] == "test":
        print index

0
5
10
15

answered Feb 27, 2018 at 6:44

Harsha BiyaniHarsha Biyani

7,0199 gold badges37 silver badges61 bronze badges

You can try :

import re
str1 = "This dress looks good; you have good taste in clothes."
substr = "good"
result = [_.start() for _ in re.finditer(substr, str1)]
# result = [17, 32]

answered Oct 25, 2021 at 10:13

When looking for a large amount of key words in a document, use flashtext

from flashtext import KeywordProcessor
words = ['test', 'exam', 'quiz']
txt = 'this is a test'
kwp = KeywordProcessor()
kwp.add_keywords_from_list(words)
result = kwp.extract_keywords(txt, span_info=True)

Flashtext runs faster than regex on large list of search words.

answered Sep 28, 2018 at 17:29

Uri GorenUri Goren

13.2k6 gold badges57 silver badges109 bronze badges

This function does not look at all positions inside the string, it does not waste compute resources. My try:

def findAll(string,word):
    all_positions=[]
    next_pos=-1
    while True:
        next_pos=string.find(word,next_pos+1)
        if(next_pos<0):
            break
        all_positions.append(next_pos)
    return all_positions

to use it call it like this:

result=findAll('this word is a big word man how many words are there?','word')

answered Jan 13, 2020 at 12:39

src = input() # we will find substring in this string
sub = input() # substring

res = []
pos = src.find(sub)
while pos != -1:
    res.append(pos)
    pos = src.find(sub, pos + 1)

answered May 16, 2020 at 17:05

mascaimascai

1,1251 gold badge8 silver badges26 bronze badges

Whatever the solutions provided by others are completely based on the available method find() or any available methods.

What is the core basic algorithm to find all the occurrences of a
substring in a string?

def find_all(string,substring):
    """
    Function: Returning all the index of substring in a string
    Arguments: String and the search string
    Return:Returning a list
    """
    length = len(substring)
    c=0
    indexes = []
    while c < len(string):
        if string[c:c+length] == substring:
            indexes.append(c)
        c=c+1
    return indexes

You can also inherit str class to new class and can use this function
below.

class newstr(str):
def find_all(string,substring):
    """
    Function: Returning all the index of substring in a string
    Arguments: String and the search string
    Return:Returning a list
    """
    length = len(substring)
    c=0
    indexes = []
    while c < len(string):
        if string[c:c+length] == substring:
            indexes.append(c)
        c=c+1
    return indexes

Calling the method

newstr.find_all(‘Do you find this answer helpful? then upvote
this!’,’this’)

answered Feb 15, 2018 at 20:02

This is solution of a similar question from hackerrank. I hope this could help you.

import re
a = input()
b = input()
if b not in a:
    print((-1,-1))
else:
    #create two list as
    start_indc = [m.start() for m in re.finditer('(?=' + b + ')', a)]
    for i in range(len(start_indc)):
        print((start_indc[i], start_indc[i]+len(b)-1))

Output:

aaadaa
aa
(0, 1)
(1, 2)
(4, 5)

answered Jan 20, 2020 at 22:47

if you want to use without re(regex) then:

find_all = lambda _str,_w : [ i for i in range(len(_str)) if _str.startswith(_w,i) ]

string = "test test test test"
print( find_all(string, 'test') ) # >>> [0, 5, 10, 15]

answered Nov 5, 2021 at 8:38

WangSungWangSung

2192 silver badges5 bronze badges

Here’s a solution that I came up with, using assignment expression (new feature since Python 3.8):

string = "test test test test"
phrase = "test"
start = -1
result = [(start := string.find(phrase, start + 1)) for _ in range(string.count(phrase))]

Output:

[0, 5, 10, 15]

answered Apr 8, 2022 at 10:06

MikeMike

1132 silver badges6 bronze badges

I think the most clean way of solution is without libraries and yields:

def find_all_occurrences(string, sub):
    index_of_occurrences = []
    current_index = 0
    while True:
        current_index = string.find(sub, current_index)
        if current_index == -1:
            return index_of_occurrences
        else:
            index_of_occurrences.append(current_index)
            current_index += len(sub)

find_all_occurrences(string, substr)

Note: find() method returns -1 when it can’t find anything

SUTerliakov

4,7063 gold badges14 silver badges36 bronze badges

answered Oct 13, 2022 at 20:06

ulas.kesikulas.kesik

1081 silver badge5 bronze badges

The pythonic way would be:

mystring = 'Hello World, this should work!'
find_all = lambda c,s: [x for x in range(c.find(s), len(c)) if c[x] == s]

# s represents the search string
# c represents the character string

find_all(mystring,'o')    # will return all positions of 'o'

[4, 7, 20, 26] 
>>>

perror

6,96316 gold badges58 silver badges84 bronze badges

answered Apr 10, 2018 at 19:40

if you only want to use numpy here is a solution

import numpy as np

S= "test test test test"
S2 = 'test'
inds = np.cumsum([len(k)+len(S2) for k in S.split(S2)[:-1]])- len(S2)
print(inds)

answered Jun 10, 2021 at 16:46

please look at below code

#!/usr/bin/env python
# coding:utf-8
'''黄哥Python'''


def get_substring_indices(text, s):
    result = [i for i in range(len(text)) if text.startswith(s, i)]
    return result


if __name__ == '__main__':
    text = "How much wood would a wood chuck chuck if a wood chuck could chuck wood?"
    s = 'wood'
    print get_substring_indices(text, s)

answered Mar 16, 2017 at 1:14

黄哥Python培训黄哥Python培训

2392 silver badges5 bronze badges

def find_index(string, let):
    enumerated = [place  for place, letter in enumerate(string) if letter == let]
    return enumerated

for example :

find_index("hey doode find d", "d")

returns:

[4, 7, 13, 15]

answered Nov 8, 2020 at 13:49

Not exactly what OP asked but you could also use the split function to get a list of where all the substrings don’t occur. OP didn’t specify the end goal of the code but if your goal is to remove the substrings anyways then this could be a simple one-liner. There are probably more efficient ways to do this with larger strings; regular expressions would be preferable in that case

# Extract all non-substrings
s = "an-example-string"
s_no_dash = s.split('-')
# >>> s_no_dash
# ['an', 'example', 'string']

# Or extract and join them into a sentence
s_no_dash2 = ' '.join(s.split('-'))
# >>> s_no_dash2
# 'an example string'

Did a brief skim of other answers so apologies if this is already up there.

answered May 19, 2021 at 13:43

als0052als0052

3893 silver badges12 bronze badges

def count_substring(string, sub_string):
    c=0
    for i in range(0,len(string)-2):
        if string[i:i+len(sub_string)] == sub_string:
            c+=1
    return c

if __name__ == '__main__':
    string = input().strip()
    sub_string = input().strip()
    
    count = count_substring(string, sub_string)
    print(count)

answered Jun 2, 2021 at 3:24

I runned in the same problem and did this:

hw = 'Hello oh World!'
list_hw = list(hw)
o_in_hw = []

while True:
    o = hw.find('o')
    if o != -1:
        o_in_hw.append(o)
        list_hw[o] = ' '
        hw = ''.join(list_hw)
    else:
        print(o_in_hw)
        break

Im pretty new at coding so you can probably simplify it (and if planned to used continuously of course make it a function).

All and all it works as intended for what i was doing.

Edit: Please consider this is for single characters only, and it will change your variable, so you have to create a copy of the string in a new variable to save it, i didnt put it in the code cause its easy and its only to show how i made it work.

answered Jun 25, 2021 at 20:18

By slicing we find all the combinations possible and append them in a list and find the number of times it occurs using count function

s=input()
n=len(s)
l=[]
f=input()
print(s[0])
for i in range(0,n):
    for j in range(1,n+1):
        l.append(s[i:j])
if f in l:
    print(l.count(f))

barbsan

3,40811 gold badges21 silver badges28 bronze badges

answered Jul 30, 2019 at 11:44

To find all the occurence of a character in a give string and return as a dictionary
eg: hello
result :
{‘h’:1, ‘e’:1, ‘l’:2, ‘o’:1}

def count(string):
   result = {}
   if(string):
     for i in string:
       result[i] = string.count(i)
     return result
   return {}

or else you do like this

from collections import Counter

   def count(string):
      return Counter(string)

answered Apr 30, 2022 at 8:00

Источник

Используйте функцию string.count() для поиска всех вхождений подстроки в строке в Python
Используйте понимание списка и startswith(), чтобы найти все вхождения подстроки в строке в Python
Используйте re.finditer(), чтобы найти все вхождения подстроки в строке в Python

Python: найти все вхождения в строке

Подстрока в Python – это набор символов, который встречается в другой строке. Работа с подстроками часто может быть проблематичной. Одна из таких проблем – найти все вхождения подстроки в определенной строке.

В этом руководстве будут рассмотрены различные методы поиска всех вхождений подстроки в строке в Python.

Используйте функцию `string.count()` для поиска всех вхождений подстроки в строке в Python

string.count() – это встроенная функция в Python, которая возвращает количество или количество вхождений подстроки в данной конкретной строке. Кроме того, в нем есть дополнительные параметры start и end для указания индексов начальной и конечной позиций.

Метод count() просматривает строку и возвращает количество раз, когда определенная подстрока встречалась в строке.

Следующий код использует функцию string.count() для поиска всех вхождений подстроки в строку.

#defining string and substring
str1 = "This dress looks good; you have good taste in clothes."
substr = "good"

#occurrence of word 'good' in whole string
count1 = str1.count(substr)
print(count1)

#occurrence of word 'good' from index 0 to 25
count2 = str1.count(substr,0,25)
print(count2)

Выход:

Это простой метод, который работает в любом случае. Единственный недостаток этого метода заключается в том, что он не возвращает различные индексы, по которым подстрока встречается в строке.

Используйте понимание списка и `startswith()`, чтобы найти все вхождения подстроки в строке в Python

Этому методу нужны две вещи: понимание списка и метод startswith().

Функция startswith() выполняет задачу получения начальных индексов подстроки, а понимание списка используется для итерации по всей целевой строке.

Следующий код использует понимание списка и startswith() для поиска всех вхождений подстроки в строку.

# defining string 
str1 = "This dress looks good; you have good taste in clothes."
  
# defining substring
substr = "good"
  
# printing original string 
print("The original string is : " + str1)
  
# printing substring 
print("The substring to find : " + substr)
  
# using list comprehension + startswith()
# All occurrences of substring in string 
res = [i for i in range(len(str1)) if str1.startswith(substr, i)]
  
# printing result 
print("The start indices of the substrings are : " + str(res))

Выход:

The original string is : This dress looks good; you have good taste in clothes.
The substring to find : good
The start indices of the substrings are : [17, 34]

Используйте `re.finditer()`, чтобы найти все вхождения подстроки в строке в Python

re.finditer() – это функция библиотеки регулярных выражений, которую Python предоставляет программистам для использования в своем коде. Это помогает в выполнении задачи поиска вхождения определенного шаблона в строке. Чтобы использовать эту функцию, нам нужно сначала импортировать библиотеку регулярных выражений re.

re.finditer() использует в своем синтаксисе параметры pattern иstring. В этом случае шаблон относится к подстроке.

Следующий код использует функцию re.finditer() для поиска всех вхождений подстроки в строку.

import re 
 
# defining string  
str1 = "This dress looks good; you have good taste in clothes."
 
#defining substring 
substr = "good"
 
print("The original string is: " + str1) 
 
print("The substring to find: " + substr) 
 
result = [_.start() for _ in re.finditer(substr, str1)] 
 
print("The start indices of the substrings are : " + str(result))

Выход:

The original string is: This dress looks good; you have good taste in clothes.
The substring to find: good
The start indices of the substrings are : [17, 34]

Источник

Часто нам нужно найти символ в строке python. Для решения этой задачи разработчики используют метод find(). Он помогает найти индекс первого совпадения подстроки в строке. Если символ или подстрока не найдены, find возвращает -1.

Синтаксис

string.find(substring,start,end)

Метод find принимает три параметра:

substring (символ/подстрока) — подстрока, которую нужно найти в данной строке.
start (необязательный) — первый индекс, с которого нужно начинать поиск. По умолчанию значение равно 0.
end (необязательный) — индекс, на котором нужно закончить поиск. По умолчанию равно длине строки.

Параметры, которые передаются в метод, — это подстрока, которую требуются найти, индекс начала и конца поиска. Значение по умолчанию для начала поиска — 0, а для конца — длина строки.

В этом примере используем метод со значениями по умолчанию.

Метод find() будет искать символ и вернет положение первого совпадения. Даже если символ встречается несколько раз, то метод вернет только положение первого совпадения.



>>> string = "Добро пожаловать!"

>>> print("Индекс первой буквы 'о':", string.find("о"))

Индекс первой буквы 'о': 1

Поиск не с начала строки с аргументом start

Можно искать подстроку, указав также начальное положение поиска.

В этом примере обозначим стартовое положение значением 8 и метод начнет искать с символа с индексом 8. Последним положением будет длина строки — таким образом метод выполнит поиска с индекса 8 до окончания строки.



>>> string = "Специалисты назвали плюсы и минусы Python"

>>> print("Индекс подстроки 'али' без учета первых 8 символов:", string.find("али", 8))

Индекс подстроки 'али' без учета первых 8 символов: 16

Поиск символа в подстроке со start и end

С помощью обоих аргументов (start и end) можно ограничить поиск и не проводить его по всей строке. Найдем индексы слова «пожаловать» и повторим поиск по букве «о».



>>> string = "Добро пожаловать!"

>>> start = string.find("п")

>>> end = string.find("ь") + 1

>>> print("Индекс первой буквы 'о' в подстроке:", string.find("о", start, end))

Индекс первой буквы 'о' в подстроке: 7

Проверка есть ли символ в строке

Мы знаем, что метод find() позволяет найти индекс первого совпадения подстроки. Он возвращает -1 в том случае, если подстрока не была найдена.



>>> string = "Добро пожаловать!"

>>> print("Есть буква 'г'?", string.find("г") != -1)

Есть буква 'г'? False

>>> print("Есть буква 'т'?", string.find("т") != -1)

Есть буква 'т'? True

Поиск последнего вхождения символа в строку

Функция rfind() напоминает find(), а единое отличие в том, что она возвращает максимальный индекс. В обоих случаях же вернется -1, если подстрока не была найдена.

В следующем примере есть строка «Добро пожаловать!». Попробуем найти в ней символ «о» с помощью методов find() и rfind().



>>> string = "Добро пожаловать"

>>> print("Поиск 'о' методом find:", string.find("о"))

Поиск 'о' методом find: 1

>>> print("Поиск 'о' методом rfind:", string.rfind("о"))

Поиск 'о' методом rfind: 11

Вывод показывает, что find() возвращает индекс первого совпадения подстроки, а rfind() — последнего совпадения.

Второй способ поиска — index()

Метод index() помогает найти положение данной подстроки по аналогии с find(). Единственное отличие в том, что index() бросит исключение в том случае, если подстрока не будет найдена, а find() просто вернет -1.

Вот рабочий пример, показывающий разницу в поведении index() и find():



>>> string = "Добро пожаловать"

>>> print("Поиск 'о' методом find:", string.find("о"))

Поиск 'о' методом find: 1

>>> print("Поиск 'о' методом index:", string.index("о"))

Поиск 'о' методом index: 1

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



>>> string = "Добро пожаловать"

>>> print("Поиск 'г' методом find:", string.find("г"))

Поиск 'г' методом find: 1

>>> print("Поиск 'г' методом index:", string.index("г"))

Traceback (most recent call last):

  File "pyshell#21", line 1, in module

    print("Поиск 'г' методом index:", string.index("г"))

ValueError: substring not found

В этом примере мы пытались найти подстроку «г». Ее там нет, поэтому find() возвращает -1, а index() бросает исключение.

Поиск всех вхождений символа в строку

Чтобы найти общее количество совпадений подстроки в строке можно использовать ту же функцию find(). Пройдемся циклом while по строке и будем задействовать параметр start из метода find().

Изначально переменная start будет равна -1, что бы прибавлять 1 у каждому новому поиску и начать с 0. Внутри цикла проверяем, присутствует ли подстрока в строке с помощью метода find.

Если вернувшееся значение не равно -1, то обновляем значением count.

Вот рабочий пример:



my_string = "Добро пожаловать"

start = -1

count = 0

while True:

    start = my_string.find("о", start+1)

    if start == -1:

        break

    count += 1


print("Количество вхождений символа в строку: ", count )

Количество вхождений символа в строку:  4

Выводы

Метод find() помогает найти индекс первого совпадения подстроки в данной строке. Возвращает -1, если подстрока не была найдена.
В метод передаются три параметра: подстрока, которую нужно найти, start со значением по умолчанию равным 0 и end со значением по умолчанию равным длине строки.
Можно искать подстроку в данной строке, задав начальное положение, с которого следует начинать поиск.
С помощью параметров start и end можно ограничить зону поиска, чтобы не выполнять его по всей строке.
Функция rfind() повторяет возможности find(), но возвращает максимальный индекс (то есть, место последнего совпадения). В обоих случаях возвращается -1, если подстрока не была найдена.
index() — еще одна функция, которая возвращает положение подстроки. Отличие лишь в том, что index() бросает исключение, если подстрока не была найдена, а find() возвращает -1.
find() можно использовать в том числе и для поиска общего числа совпадений подстроки.

Источник

Например, имеем строку “кровоточивость”, и нужно узнать индекс каждой буквы “о”,как это сделать,не переводя строку в массив?

задан 9 июн 2018 в 23:51

static void indexsCharO(String str){
    for (int i = 0; i < str.length(); i++) {
        Character value = new Character(str.charAt(i));

        if(value.equals(new Character('о')))
            System.out.print(i+" ");
    }
}

Можно сделать также чтоб результат записывался в файл,вносился в вектор и другую коллекцию, массив и что душа пожелает.
Версия по короче:

static void indexsCharO(String str){
    for(int i=0; i< str.length(); i++){
        if(str.charAt(i) == 'о') System.out.print(i);
    }
}

ответ дан 10 июн 2018 в 1:30

public static void getCharPlaces(String word, char inspectChar, int currentIndex ) {
    if(currentIndex < word.length()) {
        int up = word.indexOf(inspectChar, currentIndex) + 1;
        System.out.println("current position = " + (up - 1));
        if(up - 1 == word.lastIndexOf(inspectChar)) return;
        getCharPlaces(word, inspectChar, up);
    }
}

Ну и пример старта

getCharPlaces("кровоточивость", 'о', 0);

ответ дан 10 июн 2018 в 11:23

sanksank

3772 серебряных знака21 бронзовый знак

Источник

Алгоритмы поиска в строке

Время на прочтение
4 мин

Количество просмотров 176K

Постановка задачи поиска в строке

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)

Наиболее типичным приложением такой задачи является документальный поиск: задан фонд документов, состоящих из последовательности библиографических ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «Java». Такой запрос можно трактовать следующим образом: существуют ли статьи, обладающие дескрипторами «Программирование» и «Java».

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

Алгоритм прямого поиска

Идея алгоритма:
1. I=1,
2. сравнить I-й символ массива T с первым символом массива W,
3. совпадение → сравнить вторые символы и так далее,
4. несовпадение → I:=I+1 и переход на пункт 2,

Условие окончания алгоритма:
1. подряд М сравнений удачны,
2. I+M>N, то есть слово не найдено.

Сложность алгоритма:
Худший случай. Пусть массив T→{AAA….AAAB}, длина │T│=N, образец W→{A….AB}, длина │W│=M. Очевидно, что для обнаружения совпадения в конце строки потребуется произвести порядка N*M сравнений, то есть O(N*M).

Недостатки алгоритма:
1. высокая сложность — O(N*M), в худшем случае – Θ((N-M+1)*M);
2. после несовпадения просмотр всегда начинается с первого символа образца и поэтому может включать символы T, которые ранее уже просматривались (если строка читается из вторичной памяти, то такие возвраты занимают много времени);
3. информация о тексте T, получаемая при проверке данного сдвига S, никак не используется при проверке последующих сдвигов.

Алгоритм Д. Кнута, Д. Мориса и В. Пратта (КМП-поиск)

Алгоритм КМП-поиска фактически требует только порядка N сравнений даже в самом плохом случае.
Пример.
(Символы, подвергшиеся сравнению, подчеркнуты.)

После частичного совпадения начальной части образа W с соответствующими символами строки Т мы фактически знаем пройденную часть строки и может «вычислить» некоторые сведения (на основе самого образа W), с помощью которых потом быстро продвинемся по тексту.

Идея КМП-поиска – при каждом несовпадении двух символов текста и образа образ сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению.

Особенности КМП-поиска:
1. требуется порядка (N+M) сравнений символов для получения результата;
2. схема КМП-поиска дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае образ сдвигается более чем на единицу. К несчастью совпадения встречаются значительно реже чем несовпадения. Поэтому выигрыш от КМП-поиска в большинстве случаев текстов весьма незначителен.

Алгоритм Р. Боуера и Д. Мура (БМ-поиск)

На практике алгоритм БМ-поиска наиболее эффективен, если образец W длинный, а мощность алфавита достаточно велика.

Идея БМ-поиска – сравнение символов начинается с конца образца, а не с начала, то есть сравнение отдельных символов происходит справа налево. Затем с помощью некоторой эвристической процедуры вычисляется величина сдвига вправо s. И снова производится сравнение символов, начиная с конца образца.

Этот метод не только улучшает обработку самого плохого случая, но и даёт выигрыш в промежуточных ситуациях.
Почти всегда, кроме специально построенных примеров, БМ-поиск требует значительно меньше N сравнений. В самых же благоприятных обстоятельствах, когда последний символ образца всегда попадает на несовпадающий символ текста, число сравнений равно (N / M), в худшем же случае – О((N-M+1)*M+ p), где p – мощность алфавита.

Алгоритм Рабина-Карпа (РК-поиск)

Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│.

Пример. Пусть образец имеет вид W = 3 1 4 1 5
Вычисляем значения чисел из окна длины |W|=5 по mod q, q — простое число.

23590(mod 13)=8, 35902(mod 13)=9, 59023(mod 13)=9, …
k1=314157(mod 13) – вхождение образца,
k2=673997(mod 13) – холостое срабатывание.

Из равенства ki= kj (mod q) не следует, что ki= kj (например, 31415=67399(mod 13), но это не значит, что 31415=67399). Если ki= kj (mod q), то ещё надо проверить, совпадают ли строки W[1…m] и T[s+1…s+m] на самом деле.
Если простое число q достаточно велико, то дополнительные затраты на анализ холостых срабатываний будут невелики.
В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).

Пример: Сколько холостых срабатываний k сделает алгоритм РК, если
q= 11, 13, 17. Пусть W={2 6}

26 mod 11=4 → k =3 холостых срабатывания,
26 mod 13=0 → k =1 холостое срабатывание,
26 mod 17=9 → k =0 холостых срабатываний.

Очевидно, что количество холостых срабатываний k является функцией от величины простого числа q (если функция обработки образца mod q) и, в общем случае, от вида функции для обработки образца W и текста Т.

Источник

Example

Используйте функцию string.count() для поиска всех вхождений подстроки в строке в Python

Используйте понимание списка и startswith(), чтобы найти все вхождения подстроки в строке в Python

Используйте re.finditer(), чтобы найти все вхождения подстроки в строке в Python

Синтаксис

Поиск не с начала строки с аргументом start

Поиск символа в подстроке со start и end

Проверка есть ли символ в строке

Поиск последнего вхождения символа в строку

Второй способ поиска — index()

Поиск всех вхождений символа в строку

Выводы

Алгоритмы поиска в строке

Постановка задачи поиска в строке

Алгоритм прямого поиска

Алгоритм Д. Кнута, Д. Мориса и В. Пратта (КМП-поиск)

Алгоритм Р. Боуера и Д. Мура (БМ-поиск)

Алгоритм Рабина-Карпа (РК-поиск)

Вам также может понравиться

Как найти максимальную глубину пролива

Как найти продолжительность одного периода

Нет доступа интернет wifi на телефоне как исправить

Добавить комментарий Отменить ответ

Используйте функцию `string.count()` для поиска всех вхождений подстроки в строке в Python

Используйте понимание списка и `startswith()`, чтобы найти все вхождения подстроки в строке в Python

Используйте `re.finditer()`, чтобы найти все вхождения подстроки в строке в Python