Find The Index Of First Occurence in a String

Lecture 78 :- Find The Index Of First Occurence in a String

To find the index of the first occurrence of a substring in a string, you can use string searching algorithms like the simple brute-force method or more efficient algorithms like the Knuth-Morris-Pratt (KMP) algorithm or the Boyer-Moore algorithm. Here, I'll show you how to implement the brute-force method in Python:

pythonCopy code

def find_first_occurrence(text, pattern):    n = len(text)    m = len(pattern)    for i in range(n - m + 1):        j = 0        while j < m and text[i + j] == pattern[j]:            j += 1        if j == m:            return i    return -1 # Example usage: text = "hello world" pattern = "world" index = find_first_occurrence(text, pattern) print(index)

Output:

Copy code

6

In this example, the function find_first_occurrence takes two arguments, text (the input string) and pattern (the substring we want to find). The function iterates through the text using a sliding window of length equal to the length of the pattern. It compares the characters in the window with the characters of the pattern.

If it finds a match, it returns the starting index of the first occurrence of the pattern in the text. If there's no match, it returns -1 to indicate that the pattern is not present in the text.

Keep in mind that the brute-force method has a time complexity of O(n * m), where n is the length of the text and m is the length of the pattern. For larger texts and patterns, more efficient algorithms like KMP or Boyer-Moore should be used to improve performance.