fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. #include <vector>
  4. #include <stack>
  5. #include <queue>
  6. #include <deque>
  7. #include <utility>
  8. #include <set>
  9. #include <map>
  10. #include <unordered_set>
  11. #include <unordered_map>
  12. #include<algorithm>
  13. #include <ext/pb_ds/assoc_container.hpp>
  14. #include <ext/pb_ds/tree_policy.hpp>
  15. #define IOF ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  16. #define ll long long
  17. #define ld long double
  18. #define cy cout << "YES" << '\n';
  19. #define cn cout << "NO" << '\n';
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22.  
  23. template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  24. template<typename T>
  25. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  26.  
  27. int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
  28. int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
  29. int knightX[] = {-2, -2, 2, 2, 1, 1 , -1, -1};
  30. int knighty[] = {-1, 1, -1, 1, -2, 2, -2, 2};
  31. char di[] = {'D', 'L', 'U', 'R'};
  32. const int N =1e7+5 , M = 1e4+5;
  33. const ll mod =  1e9+7;
  34. const int LOG = 30;
  35. void FOI() {
  36.       freopen("input.txt", "r", stdin);
  37.       freopen("output.txt", "w", stdout);
  38.   }
  39. //check ur idea
  40.  
  41. int n , k ;
  42. string s;
  43. vector<vector<int>> v;
  44. vector<ll> dp;
  45. ll calc(int idx){
  46.   if(idx >= n)return 0;
  47.   ll & ret = dp[idx];
  48.   if(~ret)return ret;
  49.   ret = 1e9;
  50.   for(int i = 0 ; i < k ;i++){
  51.     auto it = upper_bound(v[i].begin() , v[i].end() , idx)- v[i].begin();
  52.     if(it >= v[i].size()){
  53.       return ret = 1;
  54.     }
  55.     ret = min(ret , calc(v[i][it])+1);
  56.   }
  57.   return ret;
  58. }
  59.  
  60. void solve(){
  61. cin >> n >> k >> s;
  62. v.resize(26);
  63. dp.resize(n);
  64. for(int i = 0 ; i < n ; i++){
  65.   v[s[i] - 'a'].push_back(i);
  66.   dp[i] = -1;
  67. }
  68. int q ; cin >> q;
  69. while(q--){
  70.   string t ; cin >> t;
  71.   int pos = -1;
  72.   bool is = false;
  73.   for (auto &&i : t)
  74.   {
  75.     int x = i-'a';
  76.    auto it = upper_bound(v[x].begin() , v[x].end() , pos) - v[x].begin();
  77.    if(it >= v[x].size()){
  78.      is = true;
  79.      break;
  80.    }
  81.    pos = v[x][it];
  82.   }
  83.   if(is){
  84.     cout << 0 << '\n';
  85.     continue;
  86.   }
  87.   cout << calc(pos) << '\n';
  88. }
  89.  
  90. }
  91.  
  92.  
  93.  
  94.  
  95.  
  96. signed main() {
  97.   IOF
  98.   //freopen("tug.in", "r", stdin);
  99.   //FOI();
  100.  
  101.     ll t = 1;
  102.    // cin >> t;
  103.     while (t--) {
  104.  
  105.     solve() ;
  106.  
  107.     }
  108.  
  109.  
  110.     return 0;
  111. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZiIz0f
language:
C++ (gcc 8.3)
created:
2 days 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!