Advertisement
Hippskill

Untitled

Jan 19th, 2016
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.53 KB | None | 0 0
  1. #define _USE_MATH_DEFINES
  2. #include<stdio.h>
  3. #include<iostream>
  4. #include<vector>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<memory.h>
  8. #include<map>
  9. #include<set>
  10. #include<queue>
  11. #include<list>
  12. #include<sstream>
  13. #include<cstring>
  14. #include<numeric>
  15. #include<limits.h>
  16. using namespace std;
  17.  
  18.  
  19. const int Pc = 1e5;
  20. const int Nc = 1e8;
  21. const int P = 8e4;
  22. const int N = 5e5;
  23.  
  24. char word[Pc];
  25. char t[Nc];
  26.  
  27. int w[P];
  28. int txt[N];
  29.  
  30. int p[3]{
  31.     1, 31, 961
  32. };
  33.  
  34.  
  35. int gethash(char a, char b, char c) {
  36.     return a + b * p[1] + c * p[2];
  37. }
  38.  
  39. map<int, int> cnt;
  40. map<int, int> cur;
  41.  
  42.  
  43. bool check() {
  44.     for (auto c : cur) {
  45.         if (cnt.count(c.first) == 0 || cnt[c.first] != c.second) {
  46.             return false;
  47.         }
  48.     }
  49.     return true;
  50. }
  51.  
  52. int main() {
  53. #ifndef ONLINE_JUDGE
  54.     freopen("input.txt", "r", stdin);
  55. #endif
  56.  
  57.     gets_s(word);
  58.     gets_s(t);
  59.  
  60.     int lenw = strlen(word);
  61.  
  62.     int id = 0;
  63.     for (int i = 0; i < lenw; i+=4) {
  64.         w[id++] = gethash(word[i], word[i + 1], word[i + 2]);
  65.     }
  66.  
  67.     for (int i = 0; i < id; i++) {
  68.         cnt[w[i]]++;
  69.     }
  70.  
  71.     int lent = strlen(t);
  72.  
  73.     int idx = 0;
  74.     for (int i = 0; i < lent; i += 4) {
  75.         txt[idx++] = gethash(t[i], t[i + 1], t[i + 2]);
  76.     }
  77.  
  78.  
  79.     if (lenw > lent) {
  80.         printf("0");
  81.         return 0;
  82.     }
  83.  
  84.     for (int i = 0; i < id; i++) {
  85.         cur[txt[i]]++;
  86.     }
  87.    
  88.     int res = 0;
  89.     if (check())
  90.         res++;
  91.  
  92.     for (int i = id; i < idx; i++) {
  93.         cur[txt[i - id]]--;
  94.         if (cur[txt[i - id]] == 0) {
  95.             cur.erase(txt[i - id]);
  96.         }
  97.         cur[txt[i]]++;
  98.         if (check())
  99.             res++;
  100.     }
  101.  
  102.     printf("%d", res);
  103.  
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement