最早的最短匹配位置

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

现在的问题是实现对于给定的字符串，将返回一个整数对，即pos和len这样matchWithMagic(substring(inputstring,pos,len))比赛和pos是数量最少，这可能是真实的（最早的比赛）的功能。当知道pos时，len是比赛最少的数字（最短匹配，优先级较低）。对效率没有要求，但答案应包括绩效分析。

例如，假设输入字符串的魔术函数返回true包含“Good Guy！”或“坏家伙！”你的功能应该返回pos=5,len=8为“好坏家伙！”。

首选语言是C/C++/Java/JavaScript/C＃/ Basic，但其他语言都可以。

UPDATE

一个平凡的答案现在已经公布。我希望能出现更有效的解决方案。

来源

2013-02-15 Earth Engine

鉴于该功能是暗箱操作，我不知道你可以做的比这更好：

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-15 06:20:54 Dukeling

其实我应该说这是正确的答案;然而这篇文章的目的不是一个微不足道的解决方案。我真的想看看是否存在更好的解决方案（更高效）。无论如何，如果没有更好的答案出现在一个星期内，我必须标记这一个。 – 2013-02-15 12:59:40

清楚地思考后，我很抱歉，我意识到这不是一个好问题。如果黑箱上没有任何假设，我相信这是我们实际可以得到的最佳答案。 – 2013-02-24 02:34:26

最早的最短匹配位置

回答

相关问题