Virtual Labs

1. What is the time complexity of Naive-String-Searching Algorithm? (N = length of string in which pattern is searched, M = length of pattern to be searched)

a: O(N*M) Explanation

Explanation

b: O(N+M) Explanation

Explanation

c: O(N^M) Explanation

Explanation

d: None of the Above. Explanation

Explanation

2. What will be the output of the following code (cpp snippet)?

string s = "kmpalgo";
int n = s.size();
string s2 = "algo";
int m = s2.size();
int i=0;
int flag = 0;
while(i{
  int j = i;
  int k = 0;
  int flag1 = 0;
  while(j  {
    if(s[j] == s2[k])
    { j++; k++; }
    else
    { flag1 = 1; break; }
  }
  if(flag1==0)
  { flag =1; break; }
  i++;
}
cout << flag << endl;

a: 1 Explanation

Explanation

b: 0 Explanation

Explanation

c: Runtime error Explanation

Explanation

d: Compilation error Explanation

Explanation

3. What is the best-case time complexity of the naive string matching algorithm?

a: O(N) Explanation

Explanation

b: O(M) Explanation

Explanation

c: O(N*M) Explanation

Explanation

d: O(1) Explanation

Explanation

4. What is the worst-case scenario for the naive string matching algorithm?

a: When the pattern and text have completely different characters Explanation

Explanation

b: When the pattern matches at the first position Explanation

Explanation

c: When the text and pattern consist of the same repeating character Explanation

Explanation

d: When the pattern is longer than the text Explanation

Explanation

5. Why is the naive algorithm called 'naive'?

a: It was invented by someone named Naive Explanation

Explanation

b: It doesn't use any preprocessing or optimization techniques Explanation

Explanation

c: It only works with simple patterns Explanation

Explanation

d: It requires the least amount of memory Explanation

Explanation

KMP Algorithm