fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n, m;
  4. string t, s;
  5.  
  6. bool check(const vector<int>& freqs, const vector<int>& freqt, int stars) {
  7.     int extneeded = 0;
  8.     for (int i = 0; i < 26; ++i) {
  9.         if (freqs[i] < freqt[i]) {
  10.             extneeded += freqt[i] - freqs[i];
  11.         }
  12.     }
  13.     return extneeded <= stars;
  14. }
  15.  
  16. void input() {
  17.     cin >> n >> m >> t >> s;
  18. }
  19.  
  20. void solve() {
  21.     vector<int> freqt(26, 0);
  22.     for (char c : t) {
  23.         freqt[c - 'a']++;
  24.     }
  25.  
  26.     vector<int> freqs(26, 0);
  27.     int stars = 0;
  28.     for (int i = 0; i < n; ++i) {
  29.         if (s[i] == '*')
  30.             stars++;
  31.         else
  32.             freqs[s[i] - 'a']++;
  33.     }
  34.  
  35.     int cnt = 0;
  36.     if (check(freqs, freqt, stars))
  37.         cnt++;
  38.  
  39.     for (int i = n; i < m; ++i) {
  40.         if (s[i - n] == '*')
  41.             stars--;
  42.         else
  43.             freqs[s[i - n] - 'a']--;
  44.  
  45.         if (s[i] == '*')
  46.             stars++;
  47.         else
  48.             freqs[s[i] - 'a']++;
  49.  
  50.         if (check(freqs, freqt, stars))
  51.             cnt++;
  52.     }
  53.  
  54.     cout << cnt << endl;
  55. }
  56.  
  57. int main() {
  58.     ios_base ::sync_with_stdio(false);
  59.     cin.tie(0);
  60.     cout.tie(0);
  61.  
  62.     if (fopen("CAU3.inp", "r")) {
  63.         freopen("CAU3.inp", "r", stdin);
  64.         freopen("CAU3.out", "w", stdout);
  65.     }
  66.  
  67.     input();
  68.     solve();
  69.  
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/CTvsap
language:
C++14 (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!