Как найти количество подстрок в строке python

Given a string and a substring, write a Python program to find how many numbers of substrings are there in the string (including overlapping cases). Let’s discuss a few methods below.

Method #1: Using re.findall() Method

Number of substrings 4

  Method #2: Using startswith() 

Number of substrings 4

Time Complexity: O(n)
Auxiliary Space: O(1)

Method #3: Using count() Method

Number of substrings 4

Method #4: Using List Comprehension

In this method, we are using a list comprehension to check if the substring is present in the main string or not. We are using the range of length of the main string minus the length of the substring plus 1. We are then checking if the substring present in the main string at the current index is equal to the given substring or not and incrementing the count accordingly.

Number of substrings 4

Time Complexity: O(n)
Auxiliary Space: O(1)

Approach#4: Using sliding window

This program uses a sliding window technique to slide a window of size m over the input string ini_str. At each step, it checks if the substring in the window is equal to sub_str, and if it is, it increments the count variable. It slides the window by iterating over the indices of the input string from 0 to n – m + 1.

Algorithm

1. Initialize count variable to 0
2. Find length of the input string ini_str and length of the substring to be counted sub_str
3. Iterate over the indices of the input string from 0 to n – m + 1
4. At each index, extract a substring of length m from ini_str
5. Compare the extracted substring with the sub_str, if it matches, increment the count variable
6. Return the count variable

Number of substrings: 4

Time complexity: O(n * m), where n is the length of the input string and m is the length of the substring to be counted. This is because the program iterates over the input string ini_str n – m + 1 times, and at each step, it extracts a substring of length m and compares it with sub_str.

Space complexity: O(1), as it only uses a constant amount of additional space to store the count variable, the length of the input string n, and the length of the substring to be counted m. It does not create any new data structures or use any additional memory proportional to the size of the input.

Last Updated :
19 Apr, 2023

Like Article

Save Article

The current best answer involving method count doesn’t really count for overlapping occurrences and doesn’t care about empty sub-strings as well.
For example:

>>> a = 'caatatab'
>>> b = 'ata'
>>> print(a.count(b)) #overlapping
1
>>>print(a.count('')) #empty string
9

The first answer should be 2 not 1, if we consider the overlapping substrings.
As for the second answer it’s better if an empty sub-string returns 0 as the asnwer.

The following code takes care of these things.

def num_of_patterns(astr,pattern):
    astr, pattern = astr.strip(), pattern.strip()
    if pattern == '': return 0

    ind, count, start_flag = 0,0,0
    while True:
        try:
            if start_flag == 0:
                ind = astr.index(pattern)
                start_flag = 1
            else:
                ind += 1 + astr[ind+1:].index(pattern)
            count += 1
        except:
            break
    return count

Now when we run it:

>>>num_of_patterns('caatatab', 'ata') #overlapping
2
>>>num_of_patterns('caatatab', '') #empty string
0
>>>num_of_patterns('abcdabcva','ab') #normal
2

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

Синтаксис:

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 "<stdin>", line 1, in <module>
# TypeError: count() takes at least 1 argument (0 given)

count() — это встроенная в Python функция, которая возвращает вам количество заданного элемента в списке или строке.

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

Синтаксис

Синтаксис Python string count() следующий:

Параметры

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

1. substring является обязательным параметром, представляющим собой строку, количество которой необходимо найти.
2. Необязательный параметр start является начальным индексом в строке, с которой начинается поиск.
3. Параметр end также необязателен и является конечным индексом в строке, где заканчивается поиск.

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

Метод Python String count() возвращает целое число, обозначающее, сколько раз подстрока встречается в данной строке.

См. следующий пример.

Здесь мы использовали ing как подстроку и проверяем, сколько раз она повторяется внутри строки. Кроме того, мы использовали формат строки для форматирования строки.

См. следующий вывод.

Использование параметров Start и End

Давайте возьмем пример, где мы передаем параметры start и end.

См. вывод приведенного выше примера.

Он будет подсчитывать количество подстрок между 11-м и 18-м символами индекса. В нашем примере ing встречается только однажды между этими символами, поэтому мы видим его один раз.

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