Substring Searching Algorithm – Multiple Choice Questions and Answers (MCQs)

Data Structures & Algorithms Computer Science & Engineering

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Substring Searching Algorithm”.

1. What will be the best case time complexity of the following code?

#include<bits/stdc++.h> 
using namespace std; 
void func(char* str2, char* str1) 
{ 
	int m = strlen(str2); 
	int n = strlen(str1); 
 
	for (int i = 0; i <= n - m; i++) 
        { 
		int j; 
 
 
		for (j = 0; j < m; j++) 
			if (str1[i + j] != str2[j]) 
				break; 
 
		if (j == m) 
			cout << i << endl; 
	} 
} 
 
int main() 
{ 
	char str1[] = "1253234"; 
	char str2[] = "323"; 
	func(str2, str1); 
	return 0; 
}

A) O(n)
B) O(m)
C) O(m * n)
D) O(m + n)

Explanation: The following code illustrates a naive pattern search system. When the first character of the pattern does not appear in the text at all, the code is at its finest. As a result, only one iteration is necessary in this case, and the time complexity will be O. (m).

2. What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
A) O(n + m)
B) O(m)
C) O(n)
D) O(m * n)

Explanation: Since it searches for patterns in linear time, the Z algorithm is an efficient pattern search algorithm. It has an O(m + n) time complexity, where m is the text length and n is the pattern length.

3. What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
A) O(n + m)
B) O(m)
C) O(n)
D) O(m * n)

Explanation: Since it searches for patterns in linear time, the Z algorithm is an efficient pattern search algorithm. It’s an O(m) auxiliary space for keeping track of the Z series.

4. The naive pattern searching algorithm is an in place algorithm.
A) true
B) false

Explanation: The complexity of the auxiliary space required by the naive pattern searching algorithm is O. (1). As a result, it is classified as an in-place algorithm.

5. Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.
A) true

B) false

Explanation: The Rabin Karp algorithm has an O(m*n) worst-case time complexity, but a linear average case time complexity. As a result, the worst-case time complexity of Rabin Karp and naive pattern searching algorithms is the same.

6. Which of the following is a sub string of “SANFOUNDRY”?
A) SANO
B) FOUND
C) SAND
D) FOND

Explanation: A substring is a string that is a subset of another. As a result, “FOUND” is the only possible substring among the options.

7. What will be the output of the following code?

#include<bits/stdc++.h> 
using namespace std; 
 
void func(char* str2, char* str1) 
{ 
	int m = strlen(str2); 
	int n = strlen(str1); 
	for (int i = 0; i <= n - m; i++) 
        { 
		int j; 
 
 
		for (j = 0; j < m; j++) 
			if (str1[i + j] != str2[j]) 
				break; 
 
		if (j == m) 
			cout << i << endl; 
	} 
} 
 
int main() 
{ 
	char str1[] = "1253234"; 
	char str2[] = "323"; 
	func(str2, str1); 
	return 0; 
}

A) 1
B) 2
C) 3
D) 4

Explanation: The following code illustrates a rudimentary method for finding a pattern in a string. As the given sub string begins at that index in the pattern, the output will be 3.

8. What will be the worst case time complexity of the following code?advertisementhttps://df76865a0d71794c8133a34b17c6f92c.safeframe.googlesyndication.com/safeframe/1-0-38/html/container.html

#include<bits/stdc++.h> 
using namespace std; 
 
void func(char* str2, char* str1) 
{ 
	int m = strlen(str2); 
	int n = strlen(str1); 
	for (int i = 0; i <= n - m; i++) 
        { 
		int j; 
 
 
		for (j = 0; j < m; j++) 
			if (str1[i + j] != str2[j]) 
				break; 
 
		if (j == m) 
			cout << i << endl; 
	} 
} 
 
int main() 
{ 
	char str1[] = "1253234"; 
	char str2[] = "323"; 
	func(str2, str1); 
	return 0; 
}

A) O(n)
B) O(m)
C) O(m * n)
D) O(m + n)

Explanation: The following code illustrates a naive pattern search system. We can deduce that the time complexity of the loop is O(m*n) by looking at the nested loop in the code.

9. What will be the auxiliary space complexity of the following code?

#include<bits/stdc++.h> 
using namespace std; 
 
void func(char* str2, char* str1) 
{ 
	int m = strlen(str2); 
	int n = strlen(str1); 
	for (int i = 0; i <= n - m; i++) 
        { 
		int j; 
 
		for (j = 0; j < m; j++) 
			if (str1[i + j] != str2[j]) 
				break; 
 
		if (j == m) 
			cout << i << endl; 
	} 
} 
 
int main() 
{ 
	char str1[] = "1253234"; 
	char str2[] = "323"; 
	func(str2, str1); 
	return 0; 
}

A) O(n)
B) O(1)
C) O(log n)
D) O(m)

Explanation: The following code illustrates a naive pattern search system. It needs O square feet of auxiliary space (1).

10. What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?
A) O(n)
B) O(n*m)
C) O(m)
D) O(log n)

Explanation: The KMP algorithm is a pattern-searching algorithm that is very efficient. It has an O(m) time complexity, where m is the text length.

A substring is a contiguous series of characters within a string in formal language theory and computer science. This is not to be confused with subsequence, which is a substring generalisation. “It was the best of times,” for example, is a subsequence but not a substring of “It was the best of times.” Python is a programming language. This is the law for string slicing: For any index I s[:i] + s[i:] == s. All of these parameters are optional; the default value for start pos is 0, end pos is the length of the string, and phase is 1. Let’s look at some basic substring creation examples using the string slice function.

Leave a Reply

Your email address will not be published. Required fields are marked *