s3 문자열 이 s1 과 s2 의 교차 로 구성 되 었 는 지 판단 합 니 다.

문자열 을 지정 하여 이 문자열 이 다른 두 문자열 로 교차 되 어 구 성 될 수 있 는 지 판단 합 니 다.

bool IsCross(char* a, char* b, char* aim)
{
	int len1 = strlen(a);
	int len2 = strlen(b);
	int len3 = strlen(aim);
	if (len3 != (len1 + len2))
		return false;

	bool **dp = new bool*[len2+1];
	int i = 0, j = 0;
	for (i = 0; i < len2+1; ++i)
		dp[i] = new bool[len1+1];
	

	for (i = 0; i <= len2;i++)
	for (j = 0; j <= len1; ++j)
		dp[i][j] = false;
	dp[0][0] = true;

	for (j = 1; j <= len1; ++j)
	{
		if (a[j - 1] != aim[j - 1])
			break;
		dp[0][j] = true;
	}
	for (i = 1; i <= len2; ++i)
	{
		if (b[i - 1] != aim[i - 1])
			break;
		dp[j][0] = true;
	}
	for (i = 1; i <= len2; ++i)
	{
		for (j = 1; j <= len1; ++j)
		{
			if ((dp[i - 1][j] == 1 && b[i - 1] == aim[i + j - 1]) || (dp[i][j - 1] == 1 && a[j - 1] == aim[i + j - 1]))
				dp[i][j] = true;
		}
	}
	return dp[len2][len1];
}
bool IsCross2(char* a, char* b, char* aim)
{
	int len1 = strlen(a);
	int len2 = strlen(b);
	int len3 = strlen(aim);
	if (len3 != (len1 + len2))
		return false;

	char* ls;
	char* ss;
	int slen;
	int llen;
	slen = len1 > len2 ? len2:len1;
	llen = len1 > len2 ? len1 : len2;
	ss = len1 > len2 ? b : a;
	ls = len1 > len2 ? a : b;

	bool* dp = new bool[slen + 1];
	for (int k = 0; k <= slen; k++)
		dp[k] = false;
	dp[0] = true;
	int i = 0, j = 0;
	for (i = 1; i <= slen; ++i)
	{
		if (ss[i - 1] != aim[i - 1])
			break;
		dp[i] = true;
	}
	for (i = 1; i <= llen; ++i)
	{
		for (j = 0; j <= slen; ++j)
		{
			if (j == 0)
			{
				dp[j] = dp[j] == false ? false : (ls[i - 1] == aim[i - 1]);
			}
			else
			{
				if ((dp[j - 1] == true && ss[j - 1] == aim[i + j - 1]) || (dp[j] == true && ls[i - 1] == aim[i + j - 1]))
					dp[j] = true;
				else
					dp[j] = false;
			}
		}
	}
	return dp[slen];
}
void main()
{
	char a[] = "AB2";
	char b[] = "12fe";
	char aim[] = "A1B2f2e";
	cout << IsCross(a, b, aim) << endl;
	cout << IsCross2(a, b, aim) << endl;
}