Advertisement
erek1e

IOI '06 P1 - Deciphering the Mayan Writing

Jul 10th, 2023
3,329
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3.  
  4. using namespace std;
  5.  
  6. inline int getID(char c) {
  7.     return ('a' <= c && c <= 'z') ? c-'a' : c-'A'+26;
  8. }
  9.  
  10. int main() {
  11.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  12.     int m, n; cin >> m >> n;
  13.     string t, s; cin >> t >> s;
  14.     int targetF[52]{}, f[52]{};
  15.     for (char c : t) ++targetF[getID(c)];
  16.     for (int i = 0; i < m-1; ++i) ++f[getID(s[i])];
  17.     int differences = 0;
  18.     for (int i = 0; i < 52; ++i) differences += targetF[i] != f[i];
  19.  
  20.     int total = 0;
  21.     for (int i = m-1; i < n; ++i) {
  22.         // add
  23.         int c = getID(s[i]);
  24.         ++f[c];
  25.         if (f[c] == targetF[c]) --differences;
  26.         else if (f[c] == targetF[c]+1) ++differences;
  27.  
  28.         // check
  29.         if (!differences) ++total;
  30.  
  31.         // remove
  32.         c = getID(s[i-m+1]);
  33.         --f[c];
  34.         if (f[c] == targetF[c]) --differences;
  35.         else if (f[c] == targetF[c]-1) ++differences;
  36.     }
  37.     cout << total << endl;
  38.     return 0;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement