Solution Exercise 56: python algorithm to find the first index of given occurrence within a given string

Exercise 56

Write a python algorithm as a function which takes a tuple of two strings (s,s1) as input and returns the index of the first occurrence of the second string 's1' within the first string 's' without using the find() method. The function must returns -1 if s1 is not found within the string s. Example if s = "Python Programming" and s1 = "thon" , the function returns the index 2.

Solution

def find_substring_index(s, s1):
    n = len(s)
    m = len(s1)
    for i in range(n - m + 1):
        j = 0
        while j < m and s[i + j] == s1[j]:
            j += 1
        if j == m:
            return i
    return -1
# Example
s = "Python Programming"
s1 = "thon"
index = find_substring_index(s, s1)
print(index)  # Output: 2

This function uses a simple algorithm to find the first occurrence of the substring s1 in the string s.

1. It starts by iterating: over all possible starting indices of s1 within s, which range from 0 to n-m, where n is the length of s and m is the length of s1.
2. At each starting index i: the function compares the characters in s starting from index i with the characters in s1.
3. If they match: it moves to the next character until either the end of s1 is reached or a mismatch is found.
4. If all characters match: the function returns the starting index i.
5. If no match is found: the function returns -1.
6. In this example: the function returns the index of the first occurrence of the substring "thon" in the string "Python Programming", which is 2.

Younes Derfoufi
my-courses.net