Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- vector<int> powers(int p, int n, int mod){
- vector<int> q(n+1);
- q[0]=1;
- for (int i=1; i<=n; i++){
- q[i]=q[i-1]*p;
- q[i]%=mod;
- }
- return q;
- }
- vector<int> hash_function(int p, int mod, string s){
- int n = (int) s.size();
- vector<int> h(n+1);
- for (int i=1; i<=n; i++){
- h[i]=h[i-1]*p+s[i-1];
- h[i]%=mod;
- }
- return h;
- }
- int hash_func(int mod, vector<int>& h, vector<int>& q, int l, int r){
- int x=h[r]-h[l]*q[r-l];
- x=((x%mod)+mod)%mod;
- return x;
- }
- int res(int mod, vector<int>& q, string s, int result, int i, char x){
- int n=(int) s.size();
- int cur=result;
- cur-=s[i]*q[n-1-i];
- cur+=x*q[n-1-i];
- cur=(cur%mod+mod)%mod;
- return cur;
- }
- signed main(){
- int mod1=1000000007;
- int mod2=1000000009;
- int p=228;
- string s, t;
- cin>>s>>t;
- int n=(int) s.size();
- int m=(int) t.size();
- vector<int> q1=powers(p, m, mod1);
- vector<int> q2=powers(p, m, mod2);
- vector<int> h1= hash_function(p, mod1, t);
- vector<int> h2= hash_function(p, mod2, t);
- unordered_set<int> pos1;
- unordered_set<int> pos2;
- int result1=0;
- int result2=0;
- for (int i=0; i<n; i++){
- result1+=s[i]*q1[n-1-i];
- result2+=s[i]*q2[n-1-i];
- result1%=mod1;
- result2%=mod2;
- }
- pos1.insert(result1);
- pos2.insert(result2);
- for (int i=0; i<n; i++){
- for (char x='A'; x<='Z'; x++){
- pos1.insert(res(mod1, q1, s, result1, i, x));
- pos2.insert(res(mod2, q2, s, result2, i, x));
- }
- for (char x='a'; x<='z'; x++){
- pos1.insert(res(mod1, q1, s, result1, i, x));
- pos2.insert(res(mod2, q2, s, result2, i, x));
- }
- }
- vector<int> ans;
- for (int i=0; i<=m-n; i++){
- if (pos1.count(hash_func(mod1, h1, q1, i, i+n)) && pos2.count(hash_func(mod2, h2, q2, i, i+n))){
- ans.push_back(i+1);
- }
- }
- cout<<ans.size()<<"\n";
- for (int x:ans){
- cout<<x<<" ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement