Implement a function with the following signature:
function bestHit(string $text, string $query): arrayThe function should implement a fairly simple form of full text search. First
argument passed to the function will contain the document to be searched, while the
second argument should be interpreted as a list of words to be found in the
document. bestHit() should return an array consisting of the starting and ending
indices of the shortest substring in the query. Both indices should be zero-indexed and inclusive. If no match could be
found, bestHit() should return an empty array.
Importantly:
Only Latin alphabetic characters (twenty six letters from A to Z in both upper
and lower case) are considered to be parts of words. Any other characters may
be present in the inputs, but should be treated as whitespace:
bestHit('some,random-text', 'random1text') === [5, 15]
Here the document is considered to consist of the words 'some', 'random' and
'text', while the query is interpreted as asking for words 'random' and 'text'.
Search should be case-insensitive:
bestHit('MATCHES', 'matches') === [0, 6]
Search should respect word boundaries:
bestHit('some,random-text', 'random1tex') === []
Here the word 'tex' in the query does not match the word 'text' in the document.
Note that word order in the query is not important, bestHit() should find
the shortest substring in the document that contains all of the search terms in
any order:
bestHit('a b... a', 'b a') === [0, 2]
Multiple non-alphabetic characters in a row should be considered as a single
word separator, but bestHit() must return the indices that could be used to
extract the desired substring from the original, untransformed $text:
bestHit('Oh, ok then!', 'OK. ...Oh.') === [0, 5]
Multiple occurences of the same word in the query should be interpreted as a
request to find a substring that contains at least that many instances of the
word in question:
bestHit('that is fine, totally', 'Fine, FINE') === []
bestHit('that is fine, totally fine.', 'Fine, FINE') === [8, 25]
bestHit() should find the shortest substring containing all the search words
in sufficient quantities in terms of the numbers of characters in this
substring, and not in the sense of the number of words in it, or any other
metric.
bestHit('a b a... a', 'a a') === [0, 4]
('a b a' contains three words, but only five characters, as opposed to
'a... a', which contains only two words, but six characters.)
In case there are multiple hits of the same length in the document, bestHit()
should return indices pointing to the first occurrence:
bestHit('a a', 'a') === [0, 0]
You may safely assume that both the document and the query will contain at least
one word, so you do not need to sanely handle the case when either of them doesn't.
Your implementation should be fairly efficient, as it will be expected to handle
a few hundred potentially large queries against ~40Kb documents in under ten
seconds.