fork download
copy 
  1. /******************************************
  2. *    AUTHOR:         BHUVNESH JAIN        *
  3. *    INSTITUITION:   BITS PILANI, PILANI  *
  4. ******************************************/
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. typedef long long LL; 
  9. typedef long double LD;
  10. typedef pair<int,int> pii;
  11.  
  12. const int MAX = 1e5 + 5;
  13. const int LIM = 50;
  14. const long long p1 = 31;
  15. const long long mod = 999999937;
  16.  
  17. int n;
  18. string s, p;
  19. map<int,vector<int>> h[LIM];
  20.  
  21. int main() {
  22. 	#ifndef ONLINE_JUDGE
  23. 		// freopen("inp.txt", "r", stdin);
  24. 	#endif
  25. 	ios_base::sync_with_stdio(false);
  26. 	cin >> s;
  27. 	n = s.length();
  28. 	int q, l, r, m;
  29. 	int a, b, c, d;
  30. 	for(int i = 0; i < n; ++i) {
  31. 		a = 0;
  32. 		for(int j = 0; j < 10; ++j) {
  33. 			if(i+j >= n) break;
  34. 			a = (1ll*a*p1)%mod + (s[i+j]-'a'+1);
  35. 			a %= mod;
  36. 			h[j][a].push_back(i);
  37. 		}
  38. 	}
  39. 	cin >> q;
  40. 	while(q--) {
  41. 		cin >> l >> r >> p;
  42. 		l -= 1;
  43. 		r -= 1;
  44. 		m = p.length();
  45. 		b = 0, c = 0;
  46. 		for(int i = 0; i < m; ++i) {
  47. 			if (p[i] == '*') {
  48. 				b += 1;
  49. 			}
  50. 			else {
  51. 				c += 1;
  52. 			}
  53. 		}
  54. 		if (b == m) {
  55. 			//all *
  56. 			printf("Yes\n");
  57. 			continue;
  58. 		}
  59. 		if (c == m && (r-l+1) > m) {
  60. 			//all alpha
  61. 			printf("No\n");
  62. 			continue;
  63. 		}
  64. 		if (c > (r-l+1)) {
  65. 			//alpha count > size of substring
  66. 			printf("No\n");
  67. 			continue;
  68. 		}
  69. 		bool ans = 1;
  70. 		int st = 0, lt = m-1;
  71. 		b = l, c = r;
  72. 		if (p[st] != '*') {
  73. 			//case of inital character(s)
  74. 			while(st < m && p[st] != '*') {
  75. 				if (p[st] != s[b]) {
  76. 					ans = 0;
  77. 					break;
  78. 				}
  79. 				b += 1;
  80. 				st += 1;
  81. 			}
  82. 			if (ans == 0) {
  83. 				printf("No\n");
  84. 				continue;
  85. 			}
  86. 		}
  87. 		if (p[lt] != '*') {
  88. 			//case of last character(s)
  89. 			while(lt >= 0 && p[lt] != '*') {
  90. 				if (p[lt] != s[c]) {
  91. 					ans = 0;
  92. 					break;
  93. 				}
  94. 				c -= 1;
  95. 				lt -= 1;
  96. 			}
  97. 			if (ans == 0) {
  98. 				printf("No\n");
  99. 				continue;
  100. 			}
  101. 		}
  102. 		//start and end character are *
  103. 		if (st <= lt) {
  104. 			assert(p[st] == '*');
  105. 			assert(p[lt] == '*');
  106. 		}
  107. 		d = b;
  108. 		for(int i = st; i < lt; ++i) {
  109. 			if (p[i] == '*') {
  110. 				int j = i;
  111. 				while(j < m && p[j] == p[i]) {
  112. 					j += 1;
  113. 				}
  114. 				i = j-1;
  115. 				continue;
  116. 			}
  117. 			//case of fixed character
  118. 			int j = i, cnt = -1;
  119. 			a = 0;
  120. 			while(j < m && p[j]!='*') {
  121. 				a = (1ll*a*p1)%mod + (p[j]-'a'+1);
  122. 				a %= mod;
  123. 				j += 1;
  124. 				cnt += 1;
  125. 			}
  126. 			auto it = lower_bound(h[cnt][a].begin(), h[cnt][a].end(), d);
  127. 			if (it == h[cnt][a].end()) {
  128. 				ans = 0;
  129. 				break;
  130. 			}
  131. 			int v = *it;
  132. 			//check if pattern doesn't cross the segment [l:r]
  133. 			if ((v+cnt) > r) {
  134. 				ans = 0;
  135. 				break;
  136. 			}
  137. 			d = v+1;
  138. 			i = j-1;
  139. 		}
  140. 		if (ans) {
  141. 			printf("Yes\n");
  142. 		}
  143. 		else {
  144. 			printf("No\n");
  145. 		}
  146. 	}
  147. 	return 0;
  148. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
abcaba
11
3 5 cab
2 4 *a*b*
2 6 b*ba
1 6 b*b*
2 5 bc*ab
1 2 a
1 6 **
1 3 a**bb**
1 3 a**b**
1 6 a*b*
1 6 a*b
stdout
copy 
Yes
No
Yes
No
Yes
No
Yes
No
Yes
Yes
No
https://ideone.com/Q5mgzO
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!