Give an efficient dynamic programming algorithm that decides if a string is an interleaving of two other strings
Let's use caps, S for input string, A for x and B for y. Furthermore, let |S| = lenS, |A| = lenA, |B| = lenB.

With any Dynamic Programming problem, it is useful to append to the problem:


  "... demonstrate one such solution." or, equivalently
  "... provide one such proof certificate."


This is because a Dynamic Programming solution is equivalent to searching over proof certificates. For this problem, what's a proof certificate? There are many possibilities. One of them is: Strings over {a, b} of length lenS. 


  Certificate aabbaa encodes: S[1] = A[1], S[2] = A[2], S[3] = B[1], S[4] = B[2], S[5] = A[3],... where array indices in A &amp; B wrap around i.e. A[r + lenA] = A[r].


Clearly, S is an interleaving of A &amp; B if and only if such a proof certificate exists. The task now boils down to finding one such certificate, if it exists.

Source code in C++ (Repl: https://repl.it/@vemana/csstackexchange#interleaving/main.cpp)

#include &lt;bits/stdc++.h&gt;

using namespace std;

const int MAX_LENS = 100, MAX_LENA=100, MAX_LENB=100;

// Memoization array
// Initialize: to -1.
int memo[MAX_LENS][MAX_LENA][MAX_LENB];

// Initialize: to 0
// Encodes the Proof Certificate, C
// SELECT[r] = 1 implies C[r] = a
// SELECT[r] = 2 implies C[r] = b
int SELECT[MAX_LENS][MAX_LENA][MAX_LENB];

// The input strings
string S, A, B;

// Initialize: lenS = S.size(), lenA = A.size(), lenB = B.size()
// Expected: lenS &gt; 0, lenA &gt; 0, lenB &gt; 0
int lenS, lenA, lenB;

vector&lt;string&gt; getCertificate() {
  if (SELECT[0][0][0] == 0)
    return vector&lt;string&gt;(); // No solution

  vector&lt;string&gt; ret(2);

  int s = 0, a = 0, b = 0;
  while(s &lt; lenS) {
    if (SELECT[s][a][b] == 1) {
      ret[0] += A[a];
      ret[1] += '_';
      a = (a+1)%lenA;
      s = s + 1;
    } else {
      ret[0] += '_';
      ret[1] += B[b];
      b = (b+1)%lenB;
      s = s + 1;
    }
  }
  return ret;
}

// Finds certificate for S[s...lenS] where
// next index in A is a (0 based)
// next index in B is b (0 based)
//
// Returns 0 if not found
// Returns 1 if found
int findCertificate(int s, int a, int b) {
  if (s == lenS)
    return 1; // Found the "empty" certificate.

  int&amp; ret = memo[s][a][b];
  if (ret != -1)  // already computed
    return ret;

  // Try to match S with A
  bool takeA = (S[s] == A[a]) &amp;&amp; findCertificate(s+1, (a+1)%lenA, b) == 1;

  // Try to match S with B
  bool takeB = (S[s] == B[b]) &amp;&amp; findCertificate(s+1, a, (b+1)%lenB) == 1;

  if (takeA) {
    SELECT[s][a][b] = 1; // SELECT A to extend the certificate
    return ret = 1;
  }

  if (takeB) {
    SELECT[s][a][b] = 2; // SELECT B to extend the certificate
    return ret = 1;
  }

  return ret = 0; // Neither matched. So, no certificate found
}

// Just run with ./a.out &lt; in
// File 'in' has three strings, one per line, representing A, B &amp; C.
int main() {
  // initialize S, A, B, lenA, lenB, lenS, SELECT, memo

  cin &gt;&gt; A;
  cin &gt;&gt; B;
  cin &gt;&gt; S;
  lenA = A.size();
  lenB = B.size();
  lenS = S.size();
  memset(memo,-1,sizeof(memo));
  memset(SELECT, 0, sizeof(SELECT));

  int out = findCertificate(0, 0, 0);
  vector&lt;string&gt; cert = getCertificate();
  string output = cert.empty() ? "NOT INTERLEAVED" : ("INTERLEAVED\n" + cert[0] + "\n" + cert[1]);
  cout &lt;&lt; output &lt;&lt; endl;
  return 0;
}