我的算法是否正确？ （字符串连接）

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的总长度，可以使用动态编程方法来解决这些问题。这些子问题中最大的问题是我们想要解决的实际问题。