# Count the Number of Occurrences of a given Substring in a String

In this article, we will learn how to count the occurrences of a substring in a string in Python. We will discuss codes having built-in functions, without built-in functions. Let's first have a quick look over what is a string in Python.

## Python String

The String is a type in python language just like integer, float, boolean, etc. Data surrounded by single quotes or double quotes are said to be a string. A string is also known as a sequence of characters.

```
string1 = "apple"
string2 = "Preeti125"
string3 = "12345"
string4 = "pre@12"
```

In Python, we can count the occurrences of a substring from a given string using three different methods. The mentioned codes will return the count of how many times a substring is present in a string.

### For Example,

## Example: Count the Occurrences of Substring using Pattern Searching Algorithm

This is a simple** **solution to match characters of a substring one by one and we increment the counter by 1 when we get the complete match for the substring. This program is generally helpful for those who are looking for an algorithm without the use of any built-in functions.

**Time Complexity:** O(M*N)

```
def count(sub, s):
M = len(sub)
N = len(s)
res = 0
# A loop to slide sub[] one by one
for i in range(N - M + 1):
# For current index i, check for the match
j = 0
while(j < M):
if (s[i + j] != sub[j]):
break
j += 1
if (j == M):
res += 1
j = 0
return res
# Driver Code
string = "abracadabra"
substring = "bra"
print("Count:", count(substring, string))
```

Count: 2

## Example: Count the Occurrences of Substring using KMP Algorithm

This solution is based on **KMP(Knuth Morris Pratt)** algorithm. The basic idea behind this algorithm is that it detects the mismatched pattern or substring instead of the matched pattern. **lps[] **array is used to skip the characters while matching. The following is a self-explanatory code. We will look into this algorithm in detail in another article.

**Time Complexity:** O(M+N)

```
def count(sub, s):
M = len(sub)
N = len(s)
# Create lps[] that will hold the longest prefix suffix values for subtern
lps = [None] * M
j = 0 # index for sub[]
# Preprocess the substring (calculate lps[] array)
lps_Array(sub, M, lps)
i = 0 # index for s[]
res = 0
next_i = 0
while (i < N):
if sub[j] == s[i]:
j = j + 1
i = i + 1
if j == M:
# When we find substring first time, we iterate again to check if there exists more substring
j = lps[j - 1]
res = res + 1
# We start i to check for more than once appearance of substring, we will reset i to previous start+1
if lps[j] != 0:
next_i = next_i + 1
i = next_i
j = 0
# Mismatch after j matches
elif ((i < N) and (sub[j] != s[i])):
# Do not match lps[0..lps[j-1]] characters, they will match anyway
if (j != 0):
j = lps[j - 1]
else:
i = i + 1
return res
def lps_Array(sub, M, lps):
# Length of the previous longest prefix suffix
len = 0
i = 1
lps[0] = 0 # lps[0] is always 0
# The loop calculates lps[i] for i = 1 to M-1
while (i < M):
if sub[i] == sub[len]:
len = len + 1
lps[i] = len
i = i + 1
else: # (sub[i] != sub[len])
# search the step
if len != 0:
len = lps[len - 1]
else: # if (len == 0)
lps[i] = len
i = i + 1
# Driver code
string = "abracadabra"
substring = "bra"
print("Count:", count(substring, string))
```

Count: 2

## Example: Count the Occurrences of Substring using count() Function

In this example, we use built-in `count()`

function to count the occurrences of the substring in the given string. It takes substring as an argument. Also, you can provide substring, start and stop arguments to find a substring within a range.

**Time Complexity:** O(n)

```
string = "abracadabra"
substring = "bra"
ct = string.count(substring)
print("Count:",ct)
```

Count: 2

### Conclusion

In this article, we learned to count the occurrences of a substring in a given string in Python by using several methods. We used some simple algorithms like pattern searching without any built-in function, KMP algorithm, and count() function to count the occurrences. We discussed that all these methods along with their time complexities.