Q1- Given an n-character input text T, suppose that all characters in the pattern P are...

Transcribed Image Text:

Q1- Given an n-character input text T, suppose that all characters in the pattern P are different. Show how to accelerate the Nave String Matcher algorithm to run faster in O(n). Assume that variable j indicates the index of the last checked character in T, before mismatch. Also consider two main scenarios where there is no match between the substrings of T and P, and when there are multiple matches between the substrings of T and pattern P. Provide your algorithm's pseudocode. T is 1-index. T:ABCO AA AB CD s=0,1,2,3,4,5,6 s=0, last checked character at j=3 before mismatch. if j>next s (here next s=1), s = j P: A B C D s=0,1,2,3,4,5,6 s=3, last checked character at location j before mismatch j= 3, if j T: ABCOAAA B C D T: ABCO AA AB CD s=0,1,2,3,4,5,6 P: A B C D s=0,1,2,3,4,5,6 s=5, last checked character at location j before mismatch j= 6, if j s=0,1,2,3,4,5,6 s=6, last checked character at location j before mismatch j= 6, if j Q2 - Prove than the time complexity of the revised algorithm in Q1 is O(n). Your answer should consider two main scenario where there is no match between the substrings of T and pattern P, and when there is multiple matches between substrings of T and pattern P. Q1- Given an n-character input text T, suppose that all characters in the pattern P are different. Show how to accelerate the Nave String Matcher algorithm to run faster in O(n). Assume that variable j indicates the index of the last checked character in T, before mismatch. Also consider two main scenarios where there is no match between the substrings of T and P, and when there are multiple matches between the substrings of T and pattern P. Provide your algorithm's pseudocode. T is 1-index. T:ABCO AA AB CD s=0,1,2,3,4,5,6 s=0, last checked character at j=3 before mismatch. if j>next s (here next s=1), s = j P: A B C D s=0,1,2,3,4,5,6 s=3, last checked character at location j before mismatch j= 3, if j T: ABCOAAA B C D T: ABCO AA AB CD s=0,1,2,3,4,5,6 P: A B C D s=0,1,2,3,4,5,6 s=5, last checked character at location j before mismatch j= 6, if j s=0,1,2,3,4,5,6 s=6, last checked character at location j before mismatch j= 6, if j Q2 - Prove than the time complexity of the revised algorithm in Q1 is O(n). Your answer should consider two main scenario where there is no match between the substrings of T and pattern P, and when there is multiple matches between substrings of T and pattern P.