我的算法是否正確？ （字符串連接）

Question

給定m個字符串和一個目標字符串t的集合S，我們想要檢查t是否是某些m字符串的連接，同時允許重複。例如：S = {ab，dbe，eaa，ea}和t = eaabdbeab。答案是肯定的，t = ea ab abbe ab。

算法：

boolean IsConcatenation{S, t, i} { 
    int a=S[i].length; 
    int b=t.length-1; 
    String str=t.charAt(1)+t.charAt(2)+...+t.charAt(a-1);` 
    if (S[i]==str) { `  
    if (i<m) //m=S.length 
     boolean A= IsConcatenation(S,t, i++); 
    t=t.charAt(a)+t.charAt(a+1)+...+t.charAt(b); 
    boolean B= IsConcatenation(S,t, 0); 
    } 
    if (i==m+1) 
    return false; 
    if (t.length==0} 
    return true; 
    return IsConcatenation(S,t, i++); 
} 

這是我的僞代碼。如果您能告訴我我的算法是正確還是不正確，我將不勝感激。

謝謝。

Answer 1

這個想法看起來正確但很慢。

某些實現細節（例如，使用i++而不是i + 1，也可能是一些錯誤的錯誤）是錯誤的，我認爲這是僞代碼，而不是任何現有語言中的代碼。

暗示一個更快的解決方案，考慮解決以下一組子問題：可以的長度k的T前綴表示一些字符串從S串聯？對於所有k，從1到T的總長度，可以使用動態編程方法來解決這些問題。這些子問題中最大的問題是我們想要解決的實際問題。