// A Dynamic Programming based program to check whether a string C is
// an interleaving of two other strings A and B.
#include <iostream>
#include <string.h>
using namespace std;
// The main function that returns true if C is
// an interleaving of A and B, otherwise false.
bool isInterleaved( char * A, char * B, char * C)
{
// Find lengths of the two strings
int M = strlen ( A) , N = strlen ( B) ;
// Let us create a 2D table to store solutions of
// 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 ;
// A is empty
else if ( i== 0 && B[ j- 1 ] == C[ j- 1 ] )
IL[ i] [ j] = IL[ i] [ j- 1 ] ;
// B is empty
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] ;
// Current character of C matches with current character of B,
// but doesn't match with current character of A
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] ;
}
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( )
{
char A[ 15 ] [ 3 ] [ 30 ] =
{
{ "abcd" , "xyz" , "axybczd" } ,
{ "AB" , "CD" , "CADB" } ,
{ "AB" ,"CD" ,"CDAB" } ,
{ "AB" , "A" , "AAB" } ,
{ "A" ,"AB" ,"ABA" } ,
{ "A" ,"AB" , "BAA" } ,
{ "ACA" ,"DAS" ,"DAACSA" } ,
{ "ACA" ,"DAS" ,"DAASCA" } ,
{ "ACA" ,"DAS" , "ADASAC" } ,
{ "A" , "AB" ,"AAB" } ,
{ "AAB" ,"AAC" ,"AACAAB" } ,
{ "101" , "01" , "10011" } ,
{ "101" ,"01" ,"11010" } ,
{ "A" ,"C" , "CA" } ,
{ "A" , "C" , "CD" }
} ;
for ( int i= 0 ; i< 15 ; ++ i)
test( A[ i] [ 0 ] , A[ i] [ 1 ] , A[ i] [ 2 ] ) ;
return 0 ;
}
Ly8gQSBEeW5hbWljIFByb2dyYW1taW5nIGJhc2VkIHByb2dyYW0gdG8gY2hlY2sgd2hldGhlciBhIHN0cmluZyBDIGlzCi8vIGFuIGludGVybGVhdmluZyBvZiB0d28gb3RoZXIgc3RyaW5ncyBBIGFuZCBCLgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxzdHJpbmcuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIFRoZSBtYWluIGZ1bmN0aW9uIHRoYXQgcmV0dXJucyB0cnVlIGlmIEMgaXMKLy8gYW4gaW50ZXJsZWF2aW5nIG9mIEEgYW5kIEIsIG90aGVyd2lzZSBmYWxzZS4KYm9vbCBpc0ludGVybGVhdmVkKGNoYXIqIEEsIGNoYXIqIEIsIGNoYXIqIEMpCnsKICAgIC8vIEZpbmQgbGVuZ3RocyBvZiB0aGUgdHdvIHN0cmluZ3MKICAgIGludCBNID0gc3RybGVuKEEpLCBOID0gc3RybGVuKEIpOwoKICAgIC8vIExldCB1cyBjcmVhdGUgYSAyRCB0YWJsZSB0byBzdG9yZSBzb2x1dGlvbnMgb2YKICAgIC8vIHN1YnByb2JsZW1zLiAgQ1tpXVtqXSB3aWxsIGJlIHRydWUgaWYgQ1swLi5pK2otMV0KICAgIC8vIGlzIGFuIGludGVybGVhdmluZyBvZiBBWzAuLmktMV0gYW5kIEJbMC4uai0xXS4KICAgIGJvb2wgSUxbTSsxXVtOKzFdOwoKICAgIG1lbXNldChJTCwgMCwgc2l6ZW9mKElMKSk7IC8vIEluaXRpYWxpemUgYWxsIHZhbHVlcyBhcyBmYWxzZS4KCiAgICAvLyBDIGNhbiBiZSBhbiBpbnRlcmxlYXZpbmcgb2YgQSBhbmQgQiBvbmx5IG9mIHN1bQogICAgLy8gb2YgbGVuZ3RocyBvZiBBICYgQiBpcyBlcXVhbCB0byBsZW5ndGggb2YgQy4KICAgIGlmICgoTStOKSAhPSBzdHJsZW4oQykpCiAgICAgICByZXR1cm4gZmFsc2U7CgogICAgLy8gUHJvY2VzcyBhbGwgY2hhcmFjdGVycyBvZiBBIGFuZCBCCiAgICBmb3IgKGludCBpPTA7IGk8PU07ICsraSkKICAgIHsKICAgICAgICBmb3IgKGludCBqPTA7IGo8PU47ICsraikKICAgICAgICB7CiAgICAgICAgICAgIC8vIHR3byBlbXB0eSBzdHJpbmdzIGhhdmUgYW4gZW1wdHkgc3RyaW5nCiAgICAgICAgICAgIC8vIGFzIGludGVybGVhdmluZwogICAgICAgICAgICBpZiAoaT09MCAmJiBqPT0wKQogICAgICAgICAgICAgICAgSUxbaV1bal0gPSB0cnVlOwoKICAgICAgICAgICAgLy8gQSBpcyBlbXB0eQogICAgICAgICAgICBlbHNlIGlmIChpPT0wICYmIEJbai0xXT09Q1tqLTFdKQogICAgICAgICAgICAgICAgSUxbaV1bal0gPSBJTFtpXVtqLTFdOwoKICAgICAgICAgICAgLy8gQiBpcyBlbXB0eQogICAgICAgICAgICBlbHNlIGlmIChqPT0wICYmIEFbaS0xXT09Q1tpLTFdKQogICAgICAgICAgICAgICAgSUxbaV1bal0gPSBJTFtpLTFdW2pdOwoKICAgICAgICAgICAgLy8gQ3VycmVudCBjaGFyYWN0ZXIgb2YgQyBtYXRjaGVzIHdpdGggY3VycmVudCBjaGFyYWN0ZXIgb2YgQSwKICAgICAgICAgICAgLy8gYnV0IGRvZXNuJ3QgbWF0Y2ggd2l0aCBjdXJyZW50IGNoYXJhY3RlciBvZiBCCiAgICAgICAgICAgIGVsc2UgaWYoQVtpLTFdPT1DW2krai0xXSAmJiBCW2otMV0hPUNbaStqLTFdKQogICAgICAgICAgICAgICAgSUxbaV1bal0gPSBJTFtpLTFdW2pdOwoKICAgICAgICAgICAgLy8gQ3VycmVudCBjaGFyYWN0ZXIgb2YgQyBtYXRjaGVzIHdpdGggY3VycmVudCBjaGFyYWN0ZXIgb2YgQiwKICAgICAgICAgICAgLy8gYnV0IGRvZXNuJ3QgbWF0Y2ggd2l0aCBjdXJyZW50IGNoYXJhY3RlciBvZiBBCiAgICAgICAgICAgIGVsc2UgaWYgKEFbaS0xXSE9Q1tpK2otMV0gJiYgQltqLTFdPT1DW2krai0xXSkKICAgICAgICAgICAgICAgIElMW2ldW2pdID0gSUxbaV1bai0xXTsKCiAgICAgICAgICAgIC8vIEN1cnJlbnQgY2hhcmFjdGVyIG9mIEMgbWF0Y2hlcyB3aXRoIHRoYXQgb2YgYm90aCBBIGFuZCBCCiAgICAgICAgICAgIGVsc2UgaWYgKEFbaS0xXT09Q1tpK2otMV0gJiYgQltqLTFdPT1DW2krai0xXSkKICAgICAgICAgICAgICAgIElMW2ldW2pdPShJTFtpLTFdW2pdIHx8IElMW2ldW2otMV0pIDsKICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIElMW01dW05dOwp9Cgp2b2lkIHRlc3QoY2hhciAqQSwgY2hhciAqQiwgY2hhciAqQykKewogICAgaWYgKGlzSW50ZXJsZWF2ZWQoQSwgQiwgQykpCiAgICAgICAgY291dCA8PCBDIDw8IiBpcyBpbnRlcmxlYXZlZCBvZiAiIDw8IEEgPDwiIGFuZCAiIDw8IEIgPDwgZW5kbDsKICAgIGVsc2UKICAgICAgICBjb3V0IDw8IEMgPDwiIGlzIG5vdCBpbnRlcmxlYXZlZCBvZiAiIDw8IEEgPDwiIGFuZCAiIDw8IEIgPDwgZW5kbDsKfQoKCi8vIERyaXZlciBwcm9ncmFtIHRvIHRlc3QgYWJvdmUgZnVuY3Rpb25zCmludCBtYWluKCkKewogICAgY2hhciBBWzE1XVszXVszMF0gPQogICAgewogICAgICAgIHsiYWJjZCIsICJ4eXoiLCAiYXh5YmN6ZCJ9LAogICAgICAgIHsiQUIiLCAiQ0QiLCAiQ0FEQiJ9LAogICAgICAgIHsiQUIiICwiQ0QiICwiQ0RBQiJ9LAogICAgICAgIHsiQUIiICwgIkEiICwgIkFBQiJ9LAogICAgICAgIHsiQSIgLCJBQiIgLCJBQkEifSwKICAgICAgICB7IkEiICwiQUIiLCAiQkFBIn0sCiAgICAgICAgeyAiQUNBIiAsIkRBUyIgLCJEQUFDU0EifSwKICAgICAgICB7IkFDQSIgLCJEQVMiICwiREFBU0NBIn0sCiAgICAgICAgeyJBQ0EiICwiREFTIiwgIkFEQVNBQyJ9LAogICAgICAgIHsiQSIsICJBQiIgLCJBQUIifSwKICAgICAgICB7IkFBQiIgLCJBQUMiICwiQUFDQUFCIn0sCiAgICAgICAgeyIxMDEiLCAiMDEiLCAiMTAwMTEifSwKICAgICAgICB7IjEwMSIgLCIwMSIgLCIxMTAxMCJ9LAogICAgICAgIHsiQSIgLCJDIiwgIkNBIn0sCiAgICAgICAgeyJBIiwgIkMiLCAiQ0QifQogICAgfTsKCiAgICBmb3IgKGludCBpPTA7IGk8MTU7ICsraSkKICAgICAgICB0ZXN0KEFbaV1bMF0sIEFbaV1bMV0sIEFbaV1bMl0pOwoKICAgICAgICByZXR1cm4gMDsKfQo=