Substring Searching Algorithm Multiple Choice Questions and Answers (MCQs)

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

1. Which of the following is a sub string of “SANFOUNDRY”?
a) SANO
b) FOUND
c) SAND
d) FOND
View Answer

Answer: b
Explanation: A sub string is a subset of another string. So “FOUND” is the only possible sub string out of the given options.

2. 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
View Answer

Answer: c
Explanation: The given code describes the naive method of finding a pattern in a string. So the output will be 3 as the given sub string begins at that index in the pattern.
advertisement
advertisement

3. What will be the worst 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)
View Answer

Answer: c
Explanation: The given code describes the naive method of pattern searching. By observing the nested loop in the code we can say that the time complexity of the loop is O(m*n).
advertisement

4. 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)
View Answer

Answer: b
Explanation: The given code describes the naive method of pattern searching. Its auxiliary space requirement is O(1).
advertisement

5. 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)
View Answer

Answer: c
Explanation: KMP algorithm is an efficient pattern searching algorithm. It has a time complexity of O(m) where m is the length of text.

6. 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)
View Answer

Answer: b
Explanation: The given code describes the naive method of pattern searching. The best case of the code occurs when the first character of the pattern does not appear in the text at all. So in such a case, only one iteration is required thus time complexity will be O(m).

7. 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)
View Answer

Answer: a
Explanation: Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It has a time complexity of O(m + n) where m is the length of text and n is the length of the pattern.

8. 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)
View Answer

Answer: b
Explanation: Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It an auxiliary space of O(m) for maintaining Z array.

9. The naive pattern searching algorithm is an in place algorithm.
a) true
b) false
View Answer

Answer: a
Explanation: The auxiliary space complexity required by naive pattern searching algorithm is O(1). So it qualifies as an in place algorithm.

10. Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.
a) true
b) false
View Answer

Answer: a
Explanation: The worst case time complexity of Rabin Karp algorithm is O(m*n) but it has a linear average case time complexity. So Rabin Karp and naive pattern searching algorithm have the same worst case time complexity.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.