Question

Here is an example of dynamic programming for a nonoptimization problem. You are trying to understand a garbled signal x that you received while conducting international wiretapping of questionable legality on behalf of of a country that prefers to remain nameless. You suspect that you actually received an interleaving of two signals. Namely, a string x is an interleaving of strings y and z if y is a substring of x, and after y is removed from x, what

Answer 1

//An interleaving of A,B,C.

bool isInterleaved(char* A, char* B, char* C)

{

    int M = strlen(A), N = strlen(B);

                                // subproblems. C[i][j] will be true if C[0..i+j-1]

                                  // is an interleaving of A[0..i-1] and B[0..j-1].

   bool IL[M+1][N+1];

  memset(IL, 0, sizeof(IL)); // Initialize all values as false.

                                // C can be an interleaving of A and B only of sum

                                  // of lengths of A & B is equal to length of C.

    if ((M+N) != strlen(C))

       return false;

                                // Process all characters of A and B

    for (int i=0; i<=M; ++i)

    {

        for (int j=0; j<=N; ++j)

        {

                                // two empty strings have an empty string

                                // as interleaving

            if (i==0 && j==0)

                IL[i][j] = true;

            else if (i==0 && B[j-1]==C[j-1])

                IL[i][j] = IL[i][j-1];

             else if (j==0 && A[i-1]==C[i-1])

                IL[i][j] = IL[i-1][j];

                           // Current character of C matches with current character of A,

                                                                // but doesn't match with current character of B

            else if(A[i-1]==C[i+j-1] && B[j-1]!=C[i+j-1])

                IL[i][j] = IL[i-1][j];

            else if (A[i-1]!=C[i+j-1] && B[j-1]==C[i+j-1])

                IL[i][j] = IL[i][j-1];

                                                                // Current character of C matches with that of both A and B

            else if (A[i-1]==C[i+j-1] && B[j-1]==C[i+j-1])

                IL[i][j]=(IL[i-1][j] || IL[i][j-1]) ;

        }

    }

    return IL[M][N];

}

// A function to run test cases

void test(char *A, char *B, char *C)

{

    if (isInterleaved(A, B, C))

        cout << C <<" is interleaved of " << A <<" and " << B << endl;

    else

        cout << C <<" is not interleaved of " << A <<" and " << B << endl;

}

// Driver program to test above functions

int main()

{

    test("XXY", "XXZ", "XXZXXXY");

    test("XY" ,"WZ" ,"WZXY");

    test ("XY", "X", "XXY");

    test ("YX", "X", "XXY");

    test ("XXY", "XXZ", "XXXXZY");

    return 0;

}