最早的最短匹配位置

假設您有一個函數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

最早的最短匹配位置

回答

相關問題