fork download
copy 
  1. //------------------------------------------Solution------------------------------------------
  2.  
  3. #include <iostream>
  4. #include <string>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. //check if character a is equal to character b
  10. bool isEqual(char a, char b) {
  11. 	if (a != '.' && b != '.' && a != b)
  12. 		return false;
  13. 	return true;
  14. }
  15.  
  16. //check if the next character of id-th character is star character or not
  17. bool getIsStar(const string &pattern, int id) {
  18. 	if (id + 1 < pattern.size())
  19. 		if (pattern[id + 1] == '*')
  20. 			return true;
  21. 	return false;
  22. }
  23.  
  24. bool solve(const string &text, const string &pattern, bool isStar, int curText, int curPattern) {
  25. 	if (curText >= text.size() && curPattern >= pattern.size())
  26. 		return true;
  27. 	if (curText >= text.size() || curPattern >= pattern.size())
  28. 		if (curText >= text.size())
  29. 			if (isStar)
  30. 				return true;	//corner case: "" ~ "a*"
  31. 			else
  32. 				return false;
  33. 		else
  34. 			return false;
  35. 	if (isStar) {
  36. 		bool result;
  37. 		//skip this star ~ "?*" is equal to ""
  38. 		result = solve(text, pattern, getIsStar(pattern, curPattern + 2), curText, curPattern + 2);
  39. 		//try all possible lenght of "?*" such as "?", "??", "???", etc.
  40. 		//increase length to check while isEqual() returns true
  41. 		for (int i = 1; curText + i <= text.size(); i++)
  42. 			if (isEqual(text[curText + i - 1], pattern[curPattern]))
  43. 				//if exist a way to make the answer true, it will be true
  44. 				//so use function max() to get the best answer
  45. 				result = max(result, solve(text, pattern, getIsStar(pattern, curPattern + 2), curText + i, curPattern + 2));
  46. 			else
  47. 				break;
  48. 		return result;
  49. 	}
  50. 	//normal case: compare two characters which are not star characters
  51. 	if (isEqual(text[curText], pattern[curPattern]))
  52. 		return solve(text, pattern, getIsStar(pattern, curPattern + 1), curText + 1, curPattern + 1);
  53. 	return false;
  54. }
  55.  
  56. bool isMatch(const string &text, const string &pattern)
  57. {
  58. 	return solve(text, pattern, getIsStar(pattern, 0), 0, 0);
  59. }
  60.  
  61. int main() {
  62. 	string text, pattern;
  63. 	cin >> text >> pattern;
  64. 	cout << (isMatch(text, pattern) ? "True" : "False");
  65. 	return 0;
  66. }
Success #stdin #stdout 0s 4476KB
comments (?)
stdin
copy 
abaa
a.*a*
stdout
copy 
True
https://ideone.com/RYwVzz
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!