String Interleave

#include<iostream>
#include<cstring>
using namespace std;

class interleaved {
	public:
		void getText(string fst, string snd, string txt) {
			if (isInterleaved(fst, snd, txt))
				cout << txt <<" is interleaved of " << fst <<" and " << snd << endl;
			else
				cout << txt <<" is not interleaved of " << fst <<" and " << snd << endl;
		}

		bool isInterleaved(string sub1, string sub2, string maintxt) {

			/* Get lengths of the strings */
			int m = sub1.length();
			int n = sub2.length();

			/* 2D array store solutions of subproblems. maintxt[i][j] will be true if maintxt[0..i+j-1] is an interleaving of sub1[0..i-1] and sub2[0..j-1]. */
			bool cache[n+1][n+1];

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

			/* 'maintxt' can be an interleaving of 'sub1' and 'sub2' only of sum of lengths of 'sub1' & 'sub2' is equal to length of 'maintxt'. */
			if ((m+n) != maintxt.length())
				return false;
			
			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)
						cache[i][j] = true;

					/* 'sub1' is empty */
					else if (i == 0 && sub2[j-1] == maintxt[j-1])
						cache[i][j] = cache[i][j-1];

					/* 'sub2' is empty */
					else if (j == 0 && sub1[i-1] == maintxt[i-1])
						cache[i][j] = cache[i-1][j];

					/* Current character of 'maintxt' matches with current character of 'sub1', but not match with current character of 'sub2' */
					else if(sub1[i-1] == maintxt[i+j-1] && sub2[j-1] != maintxt[i+j-1])
						cache[i][j] = cache[i-1][j];

					/* Current character of 'maintxt' matches with current character of 'sub2', but not match with current character of 'sub1' */
					else if (sub1[i-1] != maintxt[i+j-1] && sub2[j-1] == maintxt[i+j-1])
						cache[i][j] = cache[i][j-1];

					/* Current character of 'maintxt' matches with both 'sub1' and 'sub2' */
					else if (sub1[i-1] == maintxt[i+j-1] && sub2[j-1] == maintxt[i+j-1])
						cache[i][j] = (cache[i-1][j] || cache[i][j-1]) ;
				}
			}
			return cache[m][n];
		}

}; 


int main() {
	interleaved inleav;
	inleav.getText("ab" ,"cd" ,"abcd");
	inleav.getText("ad" ,"cb" ,"abcd");
	inleav.getText("bc", "a", "abc");
	inleav.getText("cb", "a", "aab");
	inleav.getText("abd", "bcd", "aabcd");
	return 0;
}



/* Output */
abcd is interleaved of ab and cd
abcd is not interleaved of ad and cb
abc is interleaved of bc and a
aab is not interleaved of cb and a
aabcd is not interleaved of abd and bcd