fork download
copy 
  1. #include <unordered_map>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. void cleanup(const char*s, const char*p, vector<char> &str, vector<char> &pat){
  7. 	while (*s) str.push_back(*(s++));
  8. 	while (*p) {
  9. 		if (*p != '*') pat.push_back(*(p++));
  10. 		else {
  11. 			if (!pat.size() || pat.back() != '*') pat.push_back(*(p++));
  12. 			else ++p;
  13. 		}
  14. 	}
  15. }
  16.  
  17. bool helper(int state, int offset, int strptr, int patptr, \
  18. 			vector<char> &str, vector<char> &pat, \
  19. 			unordered_multimap<int, int> &failoffset) {
  20. 	// DP part
  21. 	auto range = failoffset.equal_range(state);
  22. 	for (auto it = range.first; it != range.second; it++)
  23. 		if (it->second == offset) return false;
  24.  
  25. 	int thisoffset;
  26. 	for (thisoffset = 0; thisoffset <= str.size() - strptr; thisoffset++) {
  27. 		int tmpstrptr = strptr + thisoffset;
  28. 		int tmppatptr = patptr + 1;
  29. 		while (tmppatptr != pat.size() && tmpstrptr != str.size() && \
  30. 			pat[tmppatptr] != '*' && \
  31. 			(str[tmpstrptr] == pat[tmppatptr] || pat[tmppatptr] == '?')) {
  32. 			tmppatptr++; tmpstrptr++;
  33. 		}
  34. 		if (tmppatptr == pat.size() && tmpstrptr == str.size()) return true;
  35. 		else if (tmppatptr == pat.size()) {
  36. 			failoffset.insert(make_pair(state, offset + thisoffset));
  37. 		}
  38. 		else if (tmpstrptr == str.size()) {
  39. 			while (pat[tmppatptr] == '*' && tmppatptr < pat.size()) tmppatptr++;
  40. 			if (tmppatptr == pat.size()) return true;
  41. 			return false;
  42. 		}
  43. 		else if (pat[tmppatptr] != '*' && pat[tmppatptr] != str[tmpstrptr]) {
  44. 			failoffset.insert(make_pair(state, offset + thisoffset));
  45. 		}
  46. 		else if (pat[tmppatptr] == '*') {
  47. 			if (helper(state + 1, offset + thisoffset, tmpstrptr, tmppatptr, str, pat, failoffset))
  48. 				return true;
  49. 			failoffset.insert(make_pair(state, offset + thisoffset));
  50. 		}
  51. 	}
  52. 	failoffset.insert(make_pair(state, offset + thisoffset));
  53. 	return false;
  54. }
  55.  
  56. bool isMatch(const char*s, const char*p) {
  57. 	vector<char> str, pat;
  58. 	unordered_multimap<int, int> um;
  59. 	cleanup(s, p, str, pat);
  60. 	int i = 0;
  61. 	int j = 0;
  62. 	while (i < str.size() && j < pat.size()) {
  63. 		if (str[i] == pat[j] || pat[j] == '?') {
  64. 			i++; j++;
  65. 			continue;
  66. 		}
  67. 		if (pat[j] == '*') break;
  68. 		return false;
  69. 	}
  70. 	if (i == str.size()) {
  71. 		while (j < pat.size() && pat[j] == '*') j++;
  72. 		if (j == pat.size()) return true;
  73. 		return false;
  74. 	}
  75. 	if (j == pat.size()) return false;
  76. 	str.erase(str.begin(), str.begin() + i);
  77. 	pat.erase(pat.begin(), pat.begin() + j);
  78.  
  79. 	return helper(0, 0, 0, 0, str, pat, um);
  80. }
  81.  
  82. int main() {
  83. 	//char str[] = "abcdefg";
  84. 	//char pat[] = "ab*e*f*g*";
  85. 	char str2[] = "a";
  86. 	char pat2[] = "a*";
  87.  
  88. 	cout << isMatch(str2, pat2);
  89.  
  90. 	return 0;
  91. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/3oxSbt
wildcard match optimization 2
language:
C++14 (gcc 8.3)
created:
10 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!