fork download
  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
stdin
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
Yes
No
Yes
No
Yes
No
Yes
No
Yes
Yes
No