0

假设您有一个函数matchWithMagic返回给定字符串的布尔值。您不知道它是如何做到的任何细节，但您知道true意味着“匹配”的结果。假设这个函数的复杂度在时间和空间上与输入字符串的大小成线性关系。

现在的问题是实现一个函数，对于给定的字符串，它将返回一对整数，即pos和len这样matchWithMagic(substring(inputstring,pos,len)) 匹配并且pos是可以为真的最小数字（最早匹配）。当pos已知时，len是匹配的最小数字（最短匹配，具有较低优先级）。对效率没有要求，但答案应该包括性能分析。

例如，假设输入字符串的魔术函数 return 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 回答