非重疊最大評分序列的最佳解決方案

在開發模擬器的一部分時，我遇到了以下問題。考慮一個長度爲N的字符串，以及該字符串的M個子字符串，並將非負分數分配給它們中的每一個。特別感興趣的是滿足以下要求的子串集合：非重疊最大評分序列的最佳解決方案

它們不重疊。
他們的總分（總和，爲簡單起見）是最大的。
它們跨越整個字符串。

我明白天真的蠻力解決方案是O（M * N^2）的複雜性。雖然這個算法的實現可能不會對整個項目的性能造成太大的影響（遠離關鍵路徑，可以預先計算等），但它確實不適合我。我想知道是否有更好的解決方案來解決這個問題，如果是的話，他們是哪一個？總是欣賞指向相關代碼的指針，但只是算法描述也可以。

來源

2009-09-11 Michael Foukarakis

您是否打算按照要求3在字符串中沒有空白（未被任何子字符串覆蓋的空白字符）？ – 2009-09-11 07:23:55

這是正確的，不允許有間隙。 – 2009-09-11 07:26:27

這可以被認爲是通過DAG找到最長的路徑。字符串中的每個位置都是一個節點，每個子字符串都是一個邊。你可以通過歸納證明，對於最優路徑上的任何節點，從開始到該節點以及從該節點到結束的最佳路徑的連接與最佳路徑相同。由於這一點，您可以跟蹤每個節點的最佳路徑，並確保在開始考慮包含它的路徑之前，您已經訪問了以節點結尾的所有邊。

然後你只是有問題找到從節點開始的所有邊，或者在給定位置匹配的所有子串。如果您已經知道子字符串匹配的位置，那麼與構建哈希表一樣簡單。如果你不使用Rabin-Karp，你仍然可以建立一個哈希表。

請注意，對於O（e）複雜性，您仍然可以訪問DAG中的所有邊。或者換句話說，在開始到結束的一系列連接的子串中，你必須考慮每個子串匹配的可能性。通過對子串進行預處理以找出排除一些匹配的方法，你可以比這更好。如果能夠對此進行一般情況下的複雜性改進，並且任何實際的改進都會嚴重依賴於您的數據分佈，我還有疑問。

來源

2009-09-11 20:22:32

O（N + M）溶液：

Set f[1..N]=-1 
Set f[0]=0 
for a = 0 to N-1 
    if f[a] >= 0 
     For each substring beginning at a 
      Let b be the last index of the substring, and c its score 
      If f[a]+c > f[b+1] 
       Set f[b+1] = f[a]+c 
       Set g[b+1] = [substring number] 
Now f[N] contains the answer, or -1 if no set of substrings spans the string. 
To get the substrings: 
b = N 
while b > 0 
    Get substring number from g[N] 
    Output substring number 
    b = b - (length of substring)

來源

2009-09-11 07:06:05 jcd

這隻能提供最高分數，而不是所需的一組非重疊的子字符串。也許我應該編輯這個問題以使這一點更清楚。 – 2009-09-11 07:31:15

通過在此處並行保留'給出當前最大值'的子字符串來跟蹤集合很容易。 – 2009-09-11 07:54:37

對於M個子串，它給出的總複雜度爲O（N * M + M^2）。這通常比天真的解決方案稍微好一些，並且比我連接的O（N * logN）解決方案更糟，所以我真正想要的是對問題的肯定/否定答案，是否有比O（N * logN ）？ – 2009-09-11 08:03:16

中號子串是否給定爲在輸入字符串中的字符或的indeces的序列，但問題並沒有太大變化，因爲它是不清晰。

讓我們輸入長度爲N的輸入字符串S和M個輸入字符串Tj。令Lj爲Tj的長度，Pj - 給出字符串Sj的分數。我們說字符串

這叫做Dynamic Programming或DP。您保留一個長度爲N的整數的數組res，其中第i個元素表示如果他只有從第i個元素開始的子串（例如，如果輸入是「abcd」，那麼res [ 2]將代表你可以得到的「cd」的最高分數）。

然後，你遍歷這個數組從頭到尾，並檢查你是否可以從第i個字符開始字符串Sj。如果可以的話，那麼（res [i + Lj] + Pj）的結果顯然是可以實現的。遍歷所有Sj，res [i] = max（res [i + Lj] + Pj），可以應用於第i個字符的所有Sj。

res [0]將會是您的最終結果。

來源

2009-09-11 07:41:14 Olexiy

你應該預先計算哪些字符串可以應用到哪些位置以擺脫N^2並使你的算法O（N * M）（你應該使用一些更快的字符串搜索算法）。 – Olexiy 2009-09-11 10:50:23

我只是不明白你在哪裏得到N^2。算法是N * M - 你檢查每個N個位置的M個字符串。你能解釋一下爲什麼你認爲這是N^2 * M？ – Olexiy 2009-09-12 20:57:03

輸入：

N, the number of chars in a string 
e[0..N-1]: (b,c) an element of set e[a] means [a,b) is a substring with score c.

（如果所有子是可能的，那麼你可以只是有C（A，B）。）

通過如[1,2]我們是指覆蓋字符串第二個字母的子字符串（半開區間）。

（空子都是不允許的;如果他們成功了，那麼你可以妥善處理只有當你讓他們「考慮」最多k次）

輸出：

s[i] is the score of the best substring covering of [0,i) 
a[i]: [a[i],i) is the last substring used to cover [0,i); else NULL

算法 - 如果區間e不稀疏，則爲O（N^2）; O（N + E）其中e是允許間隔的總數。這有效地通過一個非循環圖尋找最佳路徑：

for i = 0 to N: 
    a[i] <- NULL 
    s[i] <- 0 
a[0] <- 0 
for i = 0 to N-1 
    if a[i] != NULL 
     for (b,c) in e[i]: 
      sib <- s[i]+c 
      if sib>s[b]: 
       a[b] <- i 
       s[b] <- sib

，得到最好的覆蓋三元組（A，B，C），其中的[A，B）爲c成本：

i <- N 
if (a[i]==NULL): 
    error "no covering" 
while (a[i]!=0): 
    from <- a[i] 
    yield (from,i,s[i]-s[from] 
    i <- from

當然，你可以在s [b]中存儲一對（sib，c）並保存減法。

來源

2009-09-11 08:09:56

非重疊最大評分序列的最佳解決方案

回答

相關問題