Cod sursa(job #3184394)

Utilizator Rares0netOnet Rares-Petru Rares0net Data 15 decembrie 2023 19:10:22
Problema Potrivirea sirurilor Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.11 kb
//Rares 0net
using namespace std;
using LL=long long;
#ifdef RS
    #include "Rares0.hpp"
#else
    #include<string>
    #include<vector>
    #include<fstream>
    using namespace std;
    const string N_file="strmatch";
    ifstream fin(N_file+".in");
    ofstream fout(N_file+".out");
    #define cin fin
    #define cout fout
#endif
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define f first
#define s second
#define INF 0x3f3f3f3f
void RSinit()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
}
#define MOD1 100007
#define MOD2 100021
#define v 73
pair<int, int>rollingHash(const string &str)
{
    int hash_val1, hash_val2;
    hash_val1=hash_val2=0;
    int n=str.size();
    for(int i=0; i<n; ++i)
    {
        hash_val1=(1LL*hash_val1*v+str[i])%MOD1;
        hash_val2=(1LL*hash_val2*v+str[i])%MOD2;
    }
    return mp(hash_val1, hash_val2);
}
LL ModPow(LL base, LL exp, LL mod)
{
    LL ans=1;
    while(exp>0)
    {
        if(exp%2==1)
            ans=(ans*base)%mod;
        base=(base*base)%mod;
        exp/=2;
    }
    return ans;
}
vector<int>RabinKarp(const string &str, const string &SIR)
{
    int M=str.size();
    int N=SIR.size();
    vector<int>Pos;
    pair<int, int>hash_A=rollingHash(str);
    pair<int, int>hash_B=rollingHash(SIR.substr(0, M));
    for(int i=0; i<=N-M; ++i)
    {
        if(hash_A==hash_B)
            Pos.pb(i);
        if(i<N-M)
        {
            hash_B.f=(1LL*(hash_B.f-1LL*SIR[i]*ModPow(v, M-1, MOD1))*v+SIR[i+M])%MOD1;
            hash_B.s=(1LL*(hash_B.s-1LL*SIR[i]*ModPow(v, M-1, MOD2))*v+SIR[i+M])%MOD2;
            if(hash_B.f<0)
                hash_B.f=(hash_B.f+MOD1);
            if(hash_B.s<0)
                hash_B.s=(hash_B.s+MOD2);
        }
    }
    return Pos;
}
string str, SIR;
vector<int>SolPos;
void Solve()
{
    cin>>str>>SIR;
    SolPos=RabinKarp(str, SIR);
    cout<<(int)SolPos.size()<<endl;
    for(int i=0; i<min((int)SolPos.size(), 1000); ++i)
        cout<<SolPos[i]<<' ';
}
main()
{
    RSinit();
    Solve();
}