Самое раннее короткое замыкание по команде

Question

Предполагается, что у вас есть функция matchWithMagic, которая возвращает логическое значение для данной строки. Вы не знаете, как это сделать, но вы знаете, что результат true означает «Матч». Предполагая, что сложность этой функции является линейной по времени и пространству по размеру входной строки.

Теперь вопрос заключается в реализации функции, которая для заданной строки, которая будет возвращать пару целых чисел, а именно pos и len таким образом, что matchWithMagic(substring(inputstring,pos,len)) матчи и pos наименьшее число, что это может быть правдой (ранний матч). Когда pos известно, len - наименьшее число для матча (кратчайшее совпадение с более низким приоритетом). Требования к эффективности отсутствуют, но ответ должен включать анализ эффективности.

Например, предположим, что функция magic возвращает true для входных строк, содержащих «Good Guy!». или «Плохой парень!» ваша функция должна вернуть pos=5,len=8 за «Good Bad Guy!».

Предпочтительные языки: C/C++/Java/JavaScript/C#/Basic, но на других языках все в порядке.

UPDATE

Тривиальным ответ теперь отвечал. Я надеюсь, что появится более эффективное решение.

Answer 1

Учитывая, что функция черного ящика, я не уверен, что вы можете сделать лучше, чем это:

for (int pos = 0:n) 
for (int len = 0:(n-pos)) 
    if (matchWithMagic(substring(inputstring,pos,len))) 
    return {pos, len}; 
return null; 

Что я считаю O(n^3) (предполагается, что matchWithMagic является O(n)).