Question

Python3

Big O
Problem Description:
(Pattern matching)
Write a program that prompts the user to enter two strings and tests whether the second string is a substring in the first string. Suppose the characters in the second string are distinct. (Don’t use the find method in the str class.) Analyze the time complexity of your algorithm. Your algorithm needs to be O(n) time.
Sample Run
Enter a string s1: Welcome to Python
Enter a string s2: come
matched at index 3
Analysis:
(Describe the problem including input and output in your own words.)
Design:
(?"" Describe the major steps (algorithm) for solving the problem.
Code:
Time Complexity of the Algorithm (Big O):
Test:
(Attach test cases and test results)

Answer 1

The problem is to design a Python program to determine if one string is a substring of another without using built-in methods. The solution involves a linear scanning algorithm that checks slices of the first string against the second string, and is designed to operate with O(n) time complexity. A test case confirms the correct operation of the program.

Step-by-step explanation:

Problem Description

The problem involves writing a program in Python that determines whether one string is a substring of another string without using the find method provided by the str class. The challenge is to design an efficient algorithm that operates in O(n) time complexity. This means that the time it takes to check if the second string is a substring of the first should increase linearly with the length of the first string.

Design

The algorithm can be approached by iterating through the first string (s1) and comparing a slice of it that has the same length as the second string (s2). If at any point the slice and s2 are identical, s2 is a substring of s1. If we reach the end of s1 without finding an identical slice, s2 is not a substring of s1.

Code

def is_substring(s1, s2):
for i in range(len(s1) - len(s2) + 1):
if s1[i:i+len(s2)] == s2:
return i
return -1

Time Complexity of the Algorithm (Big O)

The above algorithm is O(n) where n is the length of the first string (s1). This is because it needs to check each character in s1 at most once with respect to s2.

Test

# Test case 1
result = is_substring("Welcome to Python", "come")
# Expected: 3

The test case demonstrates that the substring "come" is found at index 3 within the string "Welcome to Python", satisfying the requirements.