Как посчитать количество вхождений символа в строке питон

Подсчёт вхождений перекрывающейся подстроки в строку

Проблема этого подхода в том, что, если у нас стоит условие найти вхождения перекрывающихся подстрок, оно работает неправильно. Например, есть строка «avava avavava» и надо найти вхождения подстроки «vav» . Код выше даст результат 2, однако, по логике, должно быть 3, так как в начале есть vav , потом два вхождения в vavav . Как это правильно реализовать?

Отслеживать
9,386 4 4 золотых знака 40 40 серебряных знаков 57 57 бронзовых знаков
задан 3 мар 2015 в 11:05
Win32Sector Win32Sector
151 1 1 золотой знак 1 1 серебряный знак 8 8 бронзовых знаков

Но ведь по логике в строке vavav одно вхождение vav. Однако если очень нужно ловить подобные случаи, то сделать не так сложно. Не трудно заметить, что в подобную ситуацию могут попадать только строки с одинаковым первым и последним символом. Можно выкидывать найденные вхождения без последнего символа из строки и проверять снова. Должно сработать.

3 мар 2015 в 11:32
жадный regexp должен помочь.
3 мар 2015 в 11:40
связанный вопрос string count with overlapping occurrences
23 дек 2017 в 14:12

6 ответов 6

Сортировка: Сброс на вариант по умолчанию

Вот версия, которая избегает излишнего копирования входной строки:

def count_overlapping_substrings(haystack, needle): count = 0 i = -1 while True: i = haystack.find(needle, i+1) if i == -1: return count count += 1 print(count_overlapping_substrings('avavrewwevavavewrewrew vavvavav ', 'vav')) # -> 6

Время исполнения — квадратичное, как и у других вариантов, которые используют str.find() метод.

Отслеживать
11 1 1 золотой знак 2 2 серебряных знака 8 8 бронзовых знаков
ответ дан 3 мар 2015 в 19:04
52.3k 11 11 золотых знаков 108 108 серебряных знаков 312 312 бронзовых знаков

Мне тоже помог этот ответ трехлетней давности, но если вы еще тут, поясните пожалуйста, как он работает? Разве string.find(substring) не возвращает номер «первого вхождения»? Непонятно как именно он считает количество вхождений?

24 июл 2018 в 22:04
@StepanSokol подумайте какой эффект имеет второй аргумент i+1 к find() .
25 июл 2018 в 3:53

я думаю i+1 стоящий на месте [start] задает индекс начала среза в исходной строке, в котором требуется отыскать подстроку. Но я не понимаю, зачем это делается?

25 июл 2018 в 12:43

@StepanSokol запустите код в отладчике и посмотрите какие значения i возвращаются. Подумайте, почему? Можно прямо в браузере на pythontutor.com по шагам пройти наблюдая за промежуточными значениями.

25 июл 2018 в 16:39

Сделал, но все равно не уловил идею, почему если старт поиска вхождения начинается с [1] индекса, то цикл находит вхождения все по очереди, даже если изменить строку и первое вхождение начнется с индекса [5], а всё то же самое, но если старт с индекса [0], то так и остается i=-1 и не хочет волшебным образом скакнуть на значение [5] соответствующее первому вхождению. Я уперся в какой-то тупик.

26 июл 2018 в 7:53

Можно, например, через регеспы и «lookahead»:

# -*- coding: utf-8 -*- import re def count_substrings(string, substring): substring_re = '(?=(%s))' % re.escape(substring) return len(re.findall(substring_re, string)) print count_substrings('avavrewwevavavewrewrew vavvavav ', 'vav') # == 6

Причем на мелких строках он медленней, чем предложенные выше варианты, но вот начиная уже с 100 символов начинает сильно выигрывать. Я потестировал скорость, тут результаты. Регекспы в 1.23 раза быстрее. С увеличением строки эта разница будет возрастать.

Отслеживать
11 1 1 золотой знак 2 2 серебряных знака 8 8 бронзовых знаков
ответ дан 3 мар 2015 в 16:49
2,475 19 19 серебряных знаков 25 25 бронзовых знаков

достоинство, что можно re применять к mmap файлу то есть к большой строке, которой не обязательно всей в памяти сидеть: sum(1 for _ in re.finditer(r'(?=<>)’.format(re.escape(‘vav’)), ‘avavrewwevavavewrewrew vavvavav ‘)) (это медленнее будет зато не ограниченно в размере)

3 мар 2015 в 18:56

Можно еще пооптимизировать: def count_substrings(string, substring): if len( substring )==1: substring_re = re.escape( substring ) else: substring_re = re.escape( substring[0] ) + «(?=» + re.escape( substring[1:] ) + «)» return len(re.findall(substring_re, string)) Должно дать выигрыш за счет оптимизации поиска практически до обычного посимвольного нативного поиска. Теоретически.

4 мар 2015 в 1:29

@ReinRaus: Для заданной строки я наблюдаю гораздо меньшие отличия: name time ratio comment count_substrings_re_opt 17.3 usec 1.00 test_string count_overlapping_substrings 19.2 usec 1.11 test_string count_overlapping_substrings_re 19.5 usec 1.13 test_string count_substrings_re 22.7 usec 1.31 test_string count_substrings 23.2 usec 1.34 test_string

4 мар 2015 в 4:37

@jfs, возможно, у нас разная разрядность систем и производительность систем в целом. Я просто хотел показать, как можно оптимизировать регулярку и достичь бОльшей производительности.

4 мар 2015 в 18:48

@ReinRaus: я достаточно уверен в процедуре измерения времени (gc выключен, минимум по трём измерениям, таймер подходящий под систему (лучшее разрешение на коротких временах). Что получается если код выполнить — два файла скачать c самими функциями и reporttime.py ?

Метод str.count() в Python, считает совпадения в строке

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

Синтаксис:

str.count(sub[, start[, end]])

Параметры:

sub — str , строка или символ;
start — int , индекс начала поиска, по умолчанию 0 , необязательно;
end — int , конец, индекс конца поиска, по умолчанию len(str) , необязательно.

Возвращаемое значение:

int , количество вхождений подстроки sub .

Описание:

Метод str.count() возвращает количество вхождений подстроки sub в строку str в диапазоне индексов [start, end] , если они переданы в метод.

Необязательные аргументы start и end интерпретируются как обозначения среза строки.
При вызове без аргументов бросает исключение TypeError (требуется как минимум 1 аргумент, передано 0 ).

Примеры подсчета количества символов/подстрок в строке.

>>> x = 'количество вхождений подстроки `sub` в диапазоне индексов' >>> x.count('и') # 5 >>> x.count('и', 6) # 4 >>> x.count('о', 10, 30) # 3 >>> x.count('`') # 2 >>> x.count('вхождений') # 1 # Без параметров >>> x.count() # Traceback (most recent call last): # File "", line 1, in # TypeError: count() takes at least 1 argument (0 given)

ОБЗОРНАЯ СТРАНИЦА РАЗДЕЛА
Метод str.capitalize(), первая буква в строке заглавная
Метод str.casefold(), сворачивает регистр строки
Метод str.center(), выравнивает строку по центру
Метод str.count(), считает совпадения в строке
Метод str.encode(), преобразует строку в байты
Метод str.endswith(), совпадение с концом строки
Метод str.expandtabs(), меняет табуляцию на пробел
Метод str.find(), индекс первого совпадения в строке
Метод str.format(), форматирует строку
Метод str.format_map()
Метод str.index(), индекс первого совпадения подстроки
Метод str.isalnum(), строка состоит из цифр и букв
Метод str.isalpha(), строка состоит только из букв
Метод str.isascii(), все символы в строке являются ASCII
Метод str.isdecimal(), проверяет строку на десятичное число
Метод str.isdigit(), строка состоит только из цифр
Метод str.isidentifier() проверяет строку на идентификатор Python
Метод str.islower( ), проверяет строку на нижний регистр
Метод str.isnumeric(), проверяет строку на числовые символы
Метод str.isprintable(), проверяет на доступность для печати
Метод str.isspace(), является ли строка пробелом
Метод str.istitle(), проверяет наличие заглавных букв в словах
Метод str.isupper(), проверяет строку на верхний регистр
Метод str.join(), объединяет список строк
Метод str.ljust(), ровняет строку по левому краю
Метод str.lower(), строку в нижний регистр
Метод str.lstrip(), обрезает символы в начале строки
Метод str.maketrans(), таблица символов для str.translate()
Метод str.partition(), делит строку по первому совпадению
Метод str.removeprefix(), удаляет префикс строки
Метод str.removesuffix(), удаляет суффикс строки
Метод str.replace(), меняет подстроку/символ в строке
Метод str.rfind(), индекс последнего совпадения подстроки
Метод str.rindex(), индекс последнего совпадения в строке
Метод str.rjust(), ровняет строку по правому краю
Метод str.rpartition(), делит строку по последнему совпадению
Метод str.rsplit(), делит строку справа
Метод str.rstrip(), обрезает символы на конце строки
Метод str.split(), делит строку по подстроке
Метод str.splitlines(), делит текст по символу ‘\n’
Метод str.startswith(), совпадение с началом строки
Метод str.strip(), обрежет строку с обоих концов
Метод str.swapcase(), сменит регистр символов в строке
Метод str.title(), каждое слово с заглавной буквы
Метод str.translate(), транслирование строки
Метод str.upper(), переведет строку в верхний регистр
Метод str.zfill(), дополнит строку нулями
Форматирование строк в стиле printf
F-string. Форматированные строки

ХОЧУ ПОМОЧЬ
ПРОЕКТУ

Python dictionary comprehension: как посчитать частоту появления каждого символа в строке?

Дана строка текста. Задача: посчитать сколько раз в ней встречается каждый символ. Предположим, я не знаю про collections.Counter и хочу написать собственную функцию, допустим вот такую:

def histogram(string): symbol_dictionary = dict() for symbol in string: if symbol in symbol_dictionary: symbol_dictionary[symbol] += 1 else: symbol_dictionary[symbol] = 1 return symbol_dictionary

Вопрос: возможно ли то же самое реализовать при помощи dictionary comprehension? И если да, то как?

Вопрос задан более года назад
349 просмотров

Python: поиск в строке

В сегодняшнем посте разбираем поиск подстроки в строке. Задачи стоят элементарнейшие. В отличие от задача по преобразованию строки в число, задачи по поиску решаются в python с помощью встроенных функций. Для решения наших задач определим строки:

# исходная строка string = "Some string for example." # подстрока, которая явно входит в исходную строку substring = "string" # подстрока, которая явно не ходит в исходную строку other_substring = "other string"

Задача №1 — узнать, входит ли подстрока в строку. Операция substring in string вернет нам в результате логический ответ: True в случае, если substring входит в строку, и False в случае, если не входит. Для наглядности приведу ниже пример.

# Для начала хотим узнать, входит ли подстрока в строку if substring in string: print ("Подстрока "%s" входит в строку "%s"" % (substring, string)) else: print ("Подстрока "%s" не входит в строку "%s"" % (substring, string)) # Та же самая процедура с другой подстрокой if other_substring in string: print ("Подстрока "%s" входит в строку "%s"" % (other_substring, string)) else: print ("Подстрока "%s" не входит в строку "%s"" % (other_substring, string))

Задача №2 — узнать позицию вхождения подстроки в строку. Данную задачу решаем с помощью функции find(self, sub[, start[, end]]). Сразу перейдем к примерам:

# Узнаем, с какой позиции подстрока входит в строку print(string.find(substring)) # 5 # Ищем, начиная с позиции 20 print(string.find(substring, 20)) # 44 # Ищем в диапазоне позиций 20 - 30 print(string.find(substring, 20, 30)) # -1 # И смотрим на результат, если подстрока не входит в строку print(string.find(other_substring)) # -1

Далее стоит перед нами задача №3 — вычислить количество вхождений подстроки в строку. С ней легко справляется функция count(self, sub[, start[, end]])

# Нам интересно количество вхождений подстроки в строку print(string.count(substring)) # 2

Задача №4 — проверить входит ли подстрока в строку без учета регистра. Для этого мы воспользуемся функцией преобразования символов строки в нижний/верхний регистр и применим к примеру №1.

# Для начала хотим узнать, входит ли подстрока в строку if substring.lower() in string.lower(): print ("Подстрока "%s" входит в строку "%s"" % (substring, string)) else: print ("Подстрока "%s" не входит в строку "%s"" % (substring, string)) # Та же самая процедура с другой подстрокой if other_substring.upper() in string.upper(): print ("Подстрока "%s" входит в строку "%s"" % (other_substring, string)) else: print ("Подстрока "%s" не входит в строку "%s"" % (other_substring, string))

На этом я остановлюсь, пожалуй. Если возникли вопросы, пожелания или предложения, то оставляйте комментарии. Отвечу всем.