Advertisement
ekzolot

Untitled

Feb 5th, 2024
677
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.12 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. vector<int> powers(int p, int n, int mod){
  5.     vector<int> q(n+1);
  6.     q[0]=1;
  7.     for (int i=1; i<=n; i++){
  8.         q[i]=q[i-1]*p;
  9.         q[i]%=mod;
  10.     }
  11.     return q;
  12. }
  13.  
  14. vector<int> hash_function(int p, int mod, string s){
  15.     int n = (int) s.size();
  16.     vector<int> h(n+1);
  17.     for (int i=1; i<=n; i++){
  18.         h[i]=h[i-1]*p+s[i-1];
  19.         h[i]%=mod;
  20.     }
  21.     return h;
  22. }
  23. int hash_func(int mod, vector<int>& h, vector<int>& q, int l, int r){
  24.     int x=h[r]-h[l]*q[r-l];
  25.     x=((x%mod)+mod)%mod;
  26.     return x;
  27. }
  28. int res(int mod, vector<int>& q, string s, int result, int i, char x){
  29.     int n=(int) s.size();
  30.     int cur=result;
  31.     cur-=s[i]*q[n-1-i];
  32.     cur+=x*q[n-1-i];
  33.     cur=(cur%mod+mod)%mod;
  34.     return cur;
  35. }
  36. signed main(){
  37.     int mod1=1000000007;
  38.     int mod2=1000000009;
  39.     int p=228;
  40.     string s, t;
  41.     cin>>s>>t;
  42.     int n=(int) s.size();
  43.     int m=(int) t.size();
  44.     vector<int> q1=powers(p, m, mod1);
  45.     vector<int> q2=powers(p, m, mod2);
  46.     vector<int> h1= hash_function(p, mod1, t);
  47.     vector<int> h2= hash_function(p, mod2, t);
  48.     unordered_set<int> pos1;
  49.     unordered_set<int> pos2;
  50.     int result1=0;
  51.     int result2=0;
  52.     for (int i=0; i<n; i++){
  53.         result1+=s[i]*q1[n-1-i];
  54.         result2+=s[i]*q2[n-1-i];
  55.         result1%=mod1;
  56.         result2%=mod2;
  57.     }
  58.     pos1.insert(result1);
  59.     pos2.insert(result2);
  60.     for (int i=0; i<n; i++){
  61.         for (char x='A'; x<='Z'; x++){
  62.             pos1.insert(res(mod1, q1, s, result1, i, x));
  63.             pos2.insert(res(mod2, q2, s, result2, i, x));
  64.         }
  65.         for (char x='a'; x<='z'; x++){
  66.             pos1.insert(res(mod1, q1, s, result1, i, x));
  67.             pos2.insert(res(mod2, q2, s, result2, i, x));
  68.         }
  69.     }
  70.     vector<int> ans;
  71.     for (int i=0; i<=m-n; i++){
  72.         if (pos1.count(hash_func(mod1, h1, q1, i, i+n)) && pos2.count(hash_func(mod2, h2, q2, i, i+n))){
  73.             ans.push_back(i+1);
  74.         }
  75.     }
  76.     cout<<ans.size()<<"\n";
  77.     for (int x:ans){
  78.         cout<<x<<" ";
  79.     }
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement