Advertisement
artemgf

Поиск шаблона в строке

May 6th, 2018
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | None | 0 0
  1. #pragma once
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #define _USE_MATH_DEFINES
  4. #include <iostream>
  5. #include <string>
  6. #include <map>
  7. #include <set>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <stdio.h>
  11. #include <cmath>
  12. #include <math.h>
  13. #include <queue>
  14. #include <stack>
  15. #include <climits>
  16. #include <deque>
  17. #include <ctime>
  18. #include <iomanip>
  19. #include <bitset>
  20. #include <unordered_map>
  21. #include <unordered_set>
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef unsigned long long ull;
  27. typedef unsigned int ui;
  28.  
  29. #define mh() make_heap()
  30. #define poph() pop_heap()
  31. #define pushh() push_heap()
  32. #define sor(n) n.begin(), n.end()
  33. #define rsor(n) n.rbegin(), n.rend()
  34. #define mp make_pair
  35. #define files freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout)
  36. #define p(T) pair<T,T>
  37. #define toch(x) cout.precision(x), cout.setf(ios::fixed)
  38. #define znac(l) abs(l)/l
  39. #define IOS ios::sync_with_stdio(false)
  40. #define IOSB cin.tie(0), cout.tie(0);
  41. const ll ok = ll(1e9 + 7);
  42.  
  43. /***
  44. фигня ищет в строке подстроку в любой её перестановки, к примеру "аб" в строке "бал"
  45. **/
  46. bool finpat(string s1, string s2)
  47. {
  48.     unordered_map<char, ll>z;
  49.     unordered_map<char, ll>g;
  50.     unordered_map<char, ll>l;
  51.     vector<vector<ll>>pr;
  52.     if (s1.size() < s2.size())
  53.     {
  54.         return 0;
  55.     }
  56.     for (int i = 0; i < s2.size(); i++)
  57.     {
  58.         z[s2[i]]++;
  59.         l[s2[i]]++;
  60.     }
  61.     ll sc = 0;
  62.     for (int i = 0; i < s2.size(); i++)
  63.     {
  64.         if (z.find(s1[i]) != z.end())
  65.         {
  66.             if (z[s1[i]] != 0)
  67.             {
  68.                 sc++;
  69.                 z[s1[i]]--;
  70.             }
  71.  
  72.         }
  73.         g[s1[i]]++;
  74.     }
  75.     if (s1.size() >= s2.size())
  76.         for (int i = 0; i < s1.size() - s2.size() + 1; i++)
  77.         {
  78.             if (sc == s2.size())
  79.             {
  80.                 return 1;
  81.             }
  82.             if (l.find(s1[i]) != l.end())
  83.             {
  84.                 if (g.find(s1[i]) != g.end())
  85.                 {
  86.                     if (g[s1[i]] - 1 < l[s1[i]])
  87.                     {
  88.                         sc--;
  89.                         z[s1[i]]++;
  90.                     }
  91.                 }
  92.             }
  93.             if (z.find(s1[i + s2.size()]) != z.end())
  94.             {
  95.                 if (z[s1[i + s2.size()]] != 0)
  96.                 {
  97.                     z[s1[i + s2.size()]]--;
  98.                     sc++;
  99.                 }
  100.             }
  101.             g[s1[i + s2.size()]]++;
  102.             g[s1[i]]--;
  103.             if (g[s1[i]] == 0)
  104.                 g.erase(s1[i]);
  105.         }
  106.     return 0;
  107. }
  108.  
  109. int main()
  110. {
  111.     IOSB;
  112.     IOS;
  113. #ifdef TheCompiler
  114.     files;
  115. #endif 
  116.     return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement