0

matchWithMagic特定の文字列に対してブール値を返す関数があるとします。それがどのように行われるか詳細はわかりませんが、true「一致」という手段の結果は知っています。この関数の複雑さは、入力文字列のサイズに対して時間と空間で線形であると仮定します。

ここでの問題は、指定された文字列に対して、整数のペアを返す関数を実装することです。つまり、pos一致 し、これが真になる最小の数です (最も早い一致)。が既知の場合、は一致の最小数です (最短一致、優先度が低くなります)。効率性に関する要件はありませんが、答えにはパフォーマンス分析が含まれている必要があります。lenmatchWithMagic(substring(inputstring,pos,len))posposlen

たとえば、入力文字列に対して true を返すマジック関数に「Good Guy!」が含まれているとします。または「バッドガイ！」あなたの関数はpos=5,len=8"Good Bad Guy!" を返します。

推奨言語は C/C++/Java/JavaScript/C#/Basic ですが、他の言語も問題ありません。

アップデート

ささいな答えが投稿されました。より効率的なソリューションが登場することを願っています。

4

1 に答える 1

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)）です。

于 2013-02-15T06:20:54.313 に答える