Give an efficient dynamic programming algorithm that decides if a string is an interleaving of two other strings I'm trying to understand this dynamic programming related problem, adapted from Kleinberg's Algorithm Design book.

You’re consulting for a group of people (who would prefer not to be
mentioned here by name) whose jobs consist of monitoring and analyzing
electronic signals coming from ships in coastal Atlantic waters. They want
a fast algorithm for a basic primitive that arises frequently: “untangling” a superposition of two known signals. Specifically, they’re picturing a situation in which each of two ships is emitting a short sequence of $0s$ and $1s$ over and over, and they want to make sure that the signal they’re hearing is simply an interleaving of these two emissions, with nothing extra added in. This describes the whole problem; we can make it a little more explicit as follows.

Given a string $x$ consisting of $0s$ and $1s$, we write $x^k$ to denote $k$ copies of $x$ concatenated together. We say that a string $x$ is a repetition of $x$ if it is a prefix of $x^k$ for some number $k$. So $x = 10110110110$ is a repetition of $x = 101$. We say that a string $s$ is an interleaving of $x$ and $y$ if its symbols can be partitioned into two (not necessarily contiguous) subsequences $s'$ and $s''$, so that $s'$ is a repetition of $x$, and $s''$ is a repetition of $y$. (So each digit in $s$ must belong to exactly one of $s'$ or $s''$.) For example, if $x = 101$ and $y = 00$, then $s = 100010101$ is an interleaving of $x$ and $y$, since characters at position $1,2,5,7,8,9$ form $101101$—a repetition of $x$—and the remaining characters form $000$—a repetition of $y$.

In terms of our application, $x$ and $y$ are the repeating sequences from the two ships, and $s$ is the signal we’re listening to: We want to make sure $s$ “unravels” into simple repetitions of $x$ and $y$. Give an efficient algorithm that takes strings $s, x,$ and $y$ and decides if $s$ is an interleaving of $x$ and $y$.
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;
}