250+ TOP MCQs on Substring Searching Algorithm and Answers

Data Structures & Algorithms Multiple Choice Questions on “Substring Searching Algorithm”.

1. Which of the following is a sub string of “”?
a) SANO
b) FOUND
c) SAND
d) FOND
Answer: b
Clarification: 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 
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

Answer: c
Clarification: 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.

3. What will be the worst case time complexity of the following code?

#include 
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)

Answer: c
Clarification: 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).

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

#include 
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)

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

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)

Answer: c
Clarification: 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 
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)

Answer: b
Clarification: 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)

Answer: a
Clarification: 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)

Answer: b
Clarification: 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

Answer: a
Clarification: 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

Answer: a
Clarification: 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.