Engineering Questions with Answers - Multiple Choice Questions

# 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

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

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)

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)

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)

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)

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)

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)

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

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