fork download
copy 
  1. /*
  2. next[i][j] = first index of character j occurring after index i, or -1 if DNE
  3. cnt[i] = # of characters required 
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. int main() {
  10. 	cin.tie(0)->sync_with_stdio(0);
  11. 		int n, k; cin >> n >> k;
  12. 		string s; cin >> s;
  13.  
  14. 		vector<vector<int>> next(n, vector<int>(k, -1));
  15.  
  16. 		for (int j = 0; j < k; j++) {
  17. 			int idx = -1;
  18. 			for (int i = n - 1; i >= 0; i--) {
  19. 				next[i][j] = idx;
  20. 				if (s[i] == (j + 'a')) idx = i;
  21. 			}
  22. 		}
  23.  
  24. 		vector<int> last(n, 0);
  25. 		map<int, int> mp; 
  26. 		for (int i = n - 1; i >= 0; i--) {
  27. 			if (mp.size() < k) {
  28. 				last[i] = 1;
  29. 			} else {
  30. 				int mn = INT_MAX;
  31. 				for (auto p : mp) mn = min(mn, p.second);
  32. 				last[i] = mn + 1;
  33. 			}
  34. 			mp[(s[i] - 'a')] = last[i];
  35. 		}
  36.  
  37. 		int q; cin >> q;
  38. 		while (q--) {
  39. 			string t; cin >> t;
  40. 			int index = t[0] == s[0] ? 0 : next[0][(t[0] - 'a')];
  41. 			int i;
  42. 			for (i = 1; i < (int) t.size() && index != -1; i++) {
  43. 				index = next[index][(t[i] - 'a')];
  44. 			}
  45. 			cout << (index == -1 ? 0 : last[index]) << '\n';	
  46. 		}
  47. }
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 1
aaaaa
6
a
aa
aaa
aaaa
aaaaa
aaaaaa
stdout
copy 
5
4
3
2
1
0
https://ideone.com/sv0jCB
language:
C++ (gcc 8.3)
created:
9 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!