Given the text The quick brown fox jumps over the lazy dog, design an algorithm that can answer many search queries efficiently. Each query contains a string and an integer k, which specifies the greatest permitted word distance between the query words.
Query words do not have to be adjacent. For example, quick fox matches because an intervening word is allowed. A distance equal to k is also valid, while a larger distance is not.
Your algorithm should return true when the query satisfies the distance requirement and false otherwise. Provide at least five test cases.
search(query: string, k: integer) -> boolean
The search text is the fixed sentence given above.
Input: query="quick", k=2
Output: true
The word quick appears in the text.
Input: query="quick fox", k=2
Output: true
quick and fox have one intervening word, giving the allowed distance of 2.
Input: query="quick jumps", k=2
Output: false
jumps is 3 words away from quick, which exceeds k.
Input: query="quick brown", k=1
Output: true
The two query words are one word-distance apart.
Input: query="brown dog", k=6
Output: true
The distance between brown and dog is 6, and equality with k is permitted.