Cod sursa(job #3217687)

Utilizator bogdann31Nicolaev Bogdan bogdann31 Data 24 martie 2024 13:06:10
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <bits/stdc++.h>
using namespace std;
#define ll                 long long 
#define all(v)             v.begin(), v.end()
ll ceil2(ll a, ll b) {
return (a + b - 1) / b;
}
long long int power(int base, int exp)
{
    if (exp == 0)
       return 1;
    else if (exp == 1)
       return base;
    else
    {
       long long int calc;
       if (exp % 2 == 0)
       {
         calc = power(base, exp/2);
         calc *= calc;
       }
       else
       {
         calc = base*power(base, exp-1);
       }
       return calc;
    }
}
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds; 
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

const int prim=101;

ll has(string s){
    ll val=0;
    for(int i=0; i<s.length(); i++){
        val+=s[i]*power(prim, i);
    }
    return val;
}

void solve(){
    string a, b;cin>>a>>b;
    ll ans=has(a);
    if(a.length()>b.length()) {cout<<0;return;}
    string s="";
    for(int i=0; i<a.length(); i++){
        s+=b[i];
    }
    ll temp=has(s);
    ll ras=0;
    // cout<<temp<<" "<<ans<<"\n";
    vector<ll> v;
    if(temp==ans) {v.push_back(0);}
    
    for(int i=a.length(); i<b.length(); i++){
        char first=s[0];
        s.erase(s.begin());
        s+=b[i];
        temp=(temp-first)/prim+b[i]*power(prim, a.length()-1);
        if(temp==ans) {v.push_back(i-a.length()+1);}
    }
    cout<<v.size()<<"\n";
    for(int i=0; i<v.size(); i++){
        cout<<v[i]<<" ";
    }

}


int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
   ios_base::sync_with_stdio(false); cin.tie(NULL);
//    ll t;cin>>t;while(t--){solve();cout<<endl;}
    solve();
}