|
Count the Number of Occurrences of a given Substring in a String PUBLISHED ON: FEBRUARY 15, 2021 Count the Number of Occurrences of a given Substring in a StringIn 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 StringThe 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,
This is a simplesolution 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))
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))
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)
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. (责任编辑：) |
