fork download
  1. /* Author : Triet Do Thanh - FPT University */
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define endl '\n'
  6. #define int long long
  7.  
  8. using namespace std;
  9.  
  10. typedef pair<int, int> ii;
  11.  
  12. const int N = 1e6 + 7;
  13. const long long oo = 1e18 + 7;
  14. const long long MOD = 1e9 + 7;
  15. const int base = 311;
  16.  
  17. int n, q, k;
  18. int dp[(1 << 15)];
  19.  
  20. int h[2][N], pw[N], a[N];
  21.  
  22. int get(int op, int l, int r) {
  23. if (op == 1) {
  24. int _l = l;
  25. l = n - r + 1;
  26. r = n - _l + 1;
  27. }
  28. return (h[op][r] - h[op][l - 1] * pw[r - l + 1] + MOD * MOD) % MOD;
  29. }
  30.  
  31. bool check(int l, int r) {
  32. return get(0, l, r) == get(1, l, r);
  33. }
  34.  
  35. #define bit(mask, i) (mask & (1ll << i))
  36. #define on(mask, i) (mask | (1ll << i))
  37. #define off(mask, i) (mask | ~(1ll << i))
  38.  
  39. void solve() {
  40. string s, t;
  41. cin >> s;
  42. n = s.size();
  43. t = s;
  44. reverse(t.begin(), t.end());
  45. s = " " + s;
  46. t = " " + t;
  47. pw[0] = 1;
  48. for (int i = 1; i <= n; ++i) {
  49. h[0][i] = (h[0][i - 1] * base + s[i] - 'a' + 1) % MOD;
  50. h[1][i] = (h[1][i - 1] * base + t[i] - 'a' + 1) % MOD;
  51. pw[i] = (pw[i - 1] * base) % MOD;
  52. }
  53. cin >> q;
  54. while (q--) {
  55. int k; cin >> k;
  56. for (int i = 1; i <= k; ++i) cin >> a[i];
  57. for (int mask = 0; mask < (1 << k); ++mask) {
  58. dp[mask] = oo;
  59. }
  60. dp[0] = 0;
  61. for (int mask = 0; mask < (1 << k); ++mask) {
  62. for (int i = 1; i <= k; ++i) {
  63. if (bit(mask, i - 1)) continue;
  64. int len = a[i];
  65. for (int j = dp[mask] + 1; j <= n - a[i] + 1; ++j) {
  66. if (check(j, j + len - 1)) {
  67. dp[on(mask, i - 1)] = min(dp[on(mask, i - 1)], j + len - 1);
  68. break;
  69. }
  70. }
  71. }
  72. }
  73. if (dp[(1 << k) - 1] != oo) cout << "YES" << endl;
  74. else cout << "NO" << endl;
  75. }
  76. }
  77.  
  78. #define TASK "test"
  79.  
  80. signed main()
  81. {
  82. ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  83. if (fopen("input.txt", "r")) {
  84. freopen("input.txt", "r", stdin);
  85. freopen("output.txt", "w", stdout);
  86. }
  87. solve();
  88. return 0;
  89. }
Success #stdin #stdout 0.01s 5584KB
stdin
Standard input is empty
stdout
Standard output is empty