String Matching
String Matching
String Matching
(https://play.google.com/store/apps/details?id=co.jones.cjzgt)
Introduction (#1617622154105-59ec4c41-97a6)
Module 6
4. What is the basic formula applied in Rabin Karp Algorithm to get the computation time as Theta(m)?
a) Halving rule
b) Horner’s rule
c) Summation lemma
d) Cancellation lemma
Answer: b
Explanation: The pattern can be evaluated in time Theta(m) using Horner’s rule:
p = P[m] + 10(P[m-1] + 10(P[m-2] +…+ 10(P[2]+10P[1])…)).
7. If n is the length of text(T) and m is the length of the pattern(P) identify the correct pre-processing algorithm. (where q is a suitable
modulus to reduce the complexity)
p=0; t0=0;
a)
for i=1 to n
do t0=(dt0 + P[i])mod q
p=(dp+T[i])mod q
b)
for i=1 to n
do p=(dp + P[i])mod q
t0=(dt0+T[i])mod q
c)
for i=1 to m
do t0=(dp + P[i])mod q
p=(dt0+T[i])mod q
d)
for i=1 to m
do p=(dp + P[i])mod q
t0=(dt0+T[i])mod q
Answer: d
Explanation: The pre-processing algorithm runs m (the length of pattern) times. This algorithm is used to compute p as the value of P[1….m] mod
q and t0 as the value of T[1….m]mod q.
8. If n is the length of text(T) and m is the length of the pattern(P) identify the correct matching algorithm.
a)
for s=0 to n
do if p=t0
then if P[1..m]=T[s+1..s+m]
then print “Pattern occurs with shift” s
b)
Answer: b
Explanation: The matching algorithm runs for n-m times. Rabin Karp algorithm explicitly verifies every valid shift. If the required pattern matches
with the given text then the algorithm prints pattern found as result.
10. Given a pattern of length-5 window, find the suitable modulo value.
43250
a) 13
b) 14
c) 12
d) 11
Answer: a
Explanation: The modulus q is typically chosen as a prime number that is large enough to reduce the complexity when p is very large.
Prepare for Aptitude with 50+ Videos Lectures and Handmade Notes
Click Here! (https://lastmomenttuitions.com/aptitude/?ref=42057)
11. Given a pattern of length- 5 window, find the valid match in the given text.
Pattern: 2 1 9 3 6
Modulus: 21
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Text: 9 2 7 2 1 8 3 0 5 7 1 2 1 2 1 9 3 6 2 3 9 7
a) 11-16
b) 3-8
c) 13-18
d) 15-20
Answer: c
Explanation: The pattern 2 1 9 3 6 occurs in the text starting from position 13 to 18. In the given pattern value is computed as 12 by having the
modulus as 21. The same text string values are computed for each possible position of a 5 length window.
12. Given a pattern of length- 5 window, find the spurious hit in the given text string.
Pattern: 3 1 4 1 5
Modulus: 13
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Text: 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1 3 9
a) 6-10
b) 12-16
c) 3-7
d) 13-17
Answer: d
Explanation: The sub string in the range 13-17, 6 7 3 9 9 produces the same value 7 as the given pattern. But the pattern numbers don’t match with
sub string identified, hence it is a spurious hit.
13. If the expected number of valid shifts is small and modulus is larger than the length of pattern what is the matching time of Rabin
Karp Algorithm?
a) Theta(m)
b) Big-Oh(n+m)
c) Theta(n-m)
d) Big-Oh(n)
Answer: b
Explanation: When the number of valid shifts(v) is Big-Oh(1) and q>=m then the matching time is given by O(n)+O(m(v+n/q)) is simplified as
O(n+m).
Prepare for Aptitude with 50+ Videos Lectures and Handmade Notes
Click Here! (https://lastmomenttuitions.com/aptitude/?ref=42057)
16. Which of the following is the fastest algorithm in string matching field?
a) Boyer-Moore’s algorithm
b) String matching algorithm
c) Quick search algorithm
d) Linear search algorithm
Answer: c
Explanation: Quick search algorithm is the fastest algorithm in string matching field whereas Linear search algorithm searches for an element in an
array of elements.
17. Which of the following algorithms formed the basis for the Quick search algorithm?
a) Boyer-Moore’s algorithm
b) Parallel string matching algorithm
c) Binary Search algorithm
d) Linear Search algorithm
Answer: a
Explanation: Quick search algorithm was originally formed to overcome the drawbacks of Boyer-Moore’s algorithm and also for increased speed
and efficiency.
Start your Machine learning & Data Science journey with Complete Hands-on Learning & doubt solving Support
Click Here! (https://lastmomenttuitions.com/python-with-machine-learning/?ref=42057)
21. Quick search algorithm starts searching from the right most character to the left.
a) true
b) false
Answer: b
Explanation: Quick search algorithm starts searching from the left most character to the right and it uses only bad character shift tables.
22. What character shift tables does Boyer-Moore’s search algorithm use?
a) good-character shift tables
b) bad-character shift tables
c) next-character shift tables
d) both good and bad character shift tables
Answer: d
Explanation: Boyer-Moore’s search algorithm uses both good and bad character shift tables whereas quick search algorithm uses only bad character
shift tables.
23. What is the worst case running time in searching phase of Boyer-Moore’s algorithm?
a) O(n)
b) O(log n)
c) O(m+n)
d) O(mn)
Answer: d
Explanation: If the pattern occurs in the text, the worst case running time of Boyer-Moore’s algorithm is found to be O(mn).
24. The searching phase in quick search algorithm has good practical behaviour.
a) true
b) false
Answer: a
Explanation: During the searching phase, the comparison between pattern and text characters can be done in any order. It has a quadratic worst case
behaviour and good practical behaviour.
25. Given input string = “ABCDABCATRYCARCABCSRT” and pattern string = “CAT”. Find the first index of the pattern match using
quick search algorithm.
a) 2
b) 6
c) 11
d) 14
Answer: b
Explanation: By using quick search algorithm, the given input text string is preprocessed and starts its search from the left most character and finds
the first occurrence of the pattern at index=2.
Python Programming for Complete Beginners
Start your Programming Journey with Python Programming which is Easy to Learn and Highly in Demand
Click Here! (https://lastmomenttuitions.com/complete-python-bootcamp/?ref=42057)
#include<bits/stdc++.h>
using namespace std;
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
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.
27. What will be the worst case time complexity of the following code?
#include<bits/stdc++.h>
using namespace std;
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
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).
28. What will be the auxiliary space complexity of the following code?
#include<bits/stdc++.h>
using namespace std;
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
Explanation: The given code describes the naive method of pattern searching. Its auxiliary space requirement is O(1).
29. 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
Explanation: KMP algorithm is an efficient pattern searching algorithm. It has a time complexity of O(m) where m is the length of text.
30. 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);
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
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).
Prepare for Aptitude with 50+ Videos Lectures and Handmade Notes
Click Here! (https://lastmomenttuitions.com/aptitude/?ref=42057)
31. 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
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.
32. 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
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.
35. The searching phase in quick search algorithm has good practical behaviour.
a. true
b. false
Answer a
true
36. If the expected number of valid shifts is small and modulus is larger than the length of pattern what is the matching time of Rabin
Karp Algorithm?
a. Theta(m)
b. Big-Oh(n+m)
c. Theta(n-m)
d. Big-Oh(n)
Answer d
Big-Oh(n+m)
Start your Machine learning & Data Science journey with Complete Hands-on Learning & doubt solving Support
Click Here! (https://lastmomenttuitions.com/python-with-machine-learning/?ref=42057)
included-mentorship/youtube-2/)
(https://lastmomenttuitions.com/course/python-zero-to-hero-covering-web-development-and-machine-learning-capstone-project-from-scratch-
included-mentorship/insta-1/)/lastmomenttuition (https://www.instagram.com/lastmomenttuition/)
(https://lastmomenttuitions.com/course/python-zero-to-hero-covering-web-development-and-machine-learning-capstone-project-from-scratch-
included-mentorship/link/)/ Last Moment Tuitions (https://in.linkedin.com/company/last-moment-
tuitions#:~:text=Last%20Moment%20Tuitions%20(LMT)%20is,others%20is%20its%20teaching%20methodology.)
(https://lastmomenttuitions.com/course/python-zero-to-hero-covering-web-development-and-machine-learning-capstone-project-from-scratch-
included-mentorship/twittrwer/)/ lastmomentdost (https://twitter.com/lastmomentdost)