Q:

Is my algorithm correct? (string concatenation)

Given a set S of m strings and a target string t we want to check whether or not t is the concatenation of some of the m strings while allowing repetition.
Example : S= {ab, dbe, eaa, ea} and t=eaabdbeab. Here the answer is YES, t=ea ab dbe ab.
Algorithm :
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++);  
}

This is my pseudo code. I would be very grateful if you could tell me whether my algorithm is correct or no.
Thank you.

A:

The idea looks correct but slow.
Some of the implementation details (for example, using i++ instead of i + 1, and also possibly some off-by-one errors) are wrong, and I believe this is pseudocode, not code in any existing language.
To hint on a faster solution, consider solving the following set of subproblems: can a prefix of T of length k be represented as a concatenation of some strings from S? These can be solved with a dynamic programming approach for all k from 1 up to the total length of T. The largest of these subproblems is the actual problem we want to solve.

