20170724 - Regular Expression Matching

std::string SimpleString(std::string s) {
	for (int i = 0; i + 3 < s.length(); i++) {
		if (s[i + 1] == s[i + 3] && s[i + 1] == '*' && s[i] == s[i + 2])
		{
			s.erase(i, 2);
			i--;
		}
	}
	return s;
}

bool CompareString(std::string s, std::string p, int i, int j) {
	int slen = s.length();
	int plen = p.length();
	bool comp;
	if (i < slen && j < plen)
	{
		comp = false;
		if (s[i] == '.' || p[j] == '.'|| s[i] == p[j]) 
		{
			comp = CompareString(s, p, i + 1, j + 1);
			if (comp) return comp;
		}
		if (p[j] == '*')
		{ 
			if (p[j - 1] == s[i] || p[j - 1] == '.') {	comp = CompareString(s, p, i , j - 1 );	if (comp) return comp;}
			comp = CompareString(s, p, i, j + 1);
			if (comp) return comp;
		}
		else if (j + 1 < plen - 1 && p[j + 1] == '*') { comp = CompareString(s, p, i, j + 2); if (comp) return comp; }
		if (s[i] == '*')
		{ 
			if (s[i - 1] == p[j] || s[i - 1] == '.') { comp = CompareString(s, p, i - 1, j);if (comp) return comp;}
			comp = CompareString(s, p, i + 1, j);
			if (comp) return comp;
		}
		else if (i + 1 < slen - 1 && s[i + 1] == '*') { comp = CompareString(s, p, i + 2, j); if (comp) return comp;}
	}
	else {
		if (i == slen && j == plen) return (s[i - 1] == p[j - 1] || s[i - 1] == '.' || p[j - 1] == '.');
		else if (i == slen && j != plen)
		{
			if (p[j] == '*' && j + 1 == plen)
			{
				return true;
			}
			else if (j + 1 != plen)
			{
				plen = plen - 1;
				while (j <= plen)
				{
					if (p[plen] != '*') return false;
					plen = plen - 2;
				}
				return true;
			}

		}

		else if (j == plen && i != slen)
		{
			if (s[i] == '*' && i + 1 == slen)
			{
				return true;
			}
			else if (i + 1 != slen)
			{
				slen = slen - 1;
				while (i <= slen)
				{
					if (s[slen] != '*') return false;
					slen = slen - 2;
				}
				return true;
			}
		}

		return false;
	}
	return comp;
}