KMP Algorithm
1. Which of the following best describes the main idea of the Naive String Searching Algorithm?
2. What is the time complexity of the Naive String Searching Algorithm? (N = length of the string, M = length of the pattern)
3. What will be the output of the following code (C++ snippet)?
string s = 'kmpalgo';
int n = s.size();
string s2 = 'algo';
int m = s2.size();
int i = 0;
int flag = 0;
while(i < n) {
int j = i;
int k = 0;
int flag1 = 0;
while(j < n && k < m) {
if(s[j] == s2[k]) { j++; k++; }
else { flag1 = 1; break; }
}
if(flag1 == 0) { flag = 1; break; }
i++;
}
cout << flag << endl;
4. Which of the following is a limitation of the Naive String Searching Algorithm compared to KMP?
5. For which scenario is the naive string searching algorithm most likely to be as efficient as KMP?