Consider a string S[1..N] of length N. You are given Q queries (Q N), where there...

Transcribed Image Text:

Consider a string S[1..N] of length N. You are given Q queries (Q≈ N), where there are three numbers l1, l2, n. The query is to determine if string S[l₁..₁ + n − 1] equals to string S[l2..l2 + n − 1] (i.e., the respective substrings starting at 1₁ and 12 and of length n match each other). 1. (10 pts) Design an algorithm to respond to these queries. Note that when analyzing the complexity, you should take the time of pre-processing and responding to queries (if any) into consideration. Consider a string S[1..N] of length N. You are given Q queries (Q≈ N), where there are three numbers l1, l2, n. The query is to determine if string S[l₁..₁ + n − 1] equals to string S[l2..l2 + n − 1] (i.e., the respective substrings starting at 1₁ and 12 and of length n match each other). 1. (10 pts) Design an algorithm to respond to these queries. Note that when analyzing the complexity, you should take the time of pre-processing and responding to queries (if any) into consideration.

Answer rating: 100% (QA)

To efficiently respond to the given queries and optimize the algorithm we can use a hashbased approa... View the full answer