Advertisement
pasholnahuy

number of permutations of string A in string B

Mar 14th, 2024
613
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <unordered_map>
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7.     string a, b;
  8.     cin >> a >> b;
  9.     unordered_map<char, int> alf_a;
  10.     for (auto el: a) {
  11.         ++alf_a[el];
  12.     }
  13.     int cur_diff = alf_a.size();
  14.     unordered_map<char, int> cur_alf;
  15.     int ans = 0;
  16.     for (int i = 0; i < a.size(); ++i) {
  17.         ++cur_alf[b[i]];
  18.         if (cur_alf[b[i]] == alf_a[b[i]]) {
  19.             --cur_diff;
  20.         } else if (cur_alf[b[i]] - 1 == alf_a[b[i]]) {
  21.             ++cur_diff;
  22.         }
  23.         if (cur_diff == 0) ++ans;
  24.     }
  25.     for (int i = 0; i + a.size() < b.size(); ++i) {
  26.         --cur_alf[b[i]];
  27.         if (cur_alf[b[i]] == alf_a[b[i]]) {
  28.             --cur_diff;
  29.         } else if (cur_alf[b[i]] + 1 == alf_a[b[i]]) {
  30.             ++cur_diff;
  31.         }
  32.         ++cur_alf[b[i + a.size()]];
  33.         if (cur_alf[b[i + a.size()]] == alf_a[b[i + a.size()]]) {
  34.             --cur_diff;
  35.         } else if (cur_alf[b[i + a.size()]] - 1 == alf_a[b[i + a.size()]]) {
  36.             ++cur_diff;
  37.         }
  38.         if (cur_diff == 0) ++ans;
  39.     }
  40.     cout << ans;
  41. }
  42. //abbac
  43.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement