Substring Searching Algorithm MCQ’s

1 - Question

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 - Question

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.

3 - Question

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

4 - Question

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

5 - Question

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 - Question

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 - Question

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 - Question

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 - Question

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 - Question

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.

Substring Searching Algorithm MCQ’s

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners