Cod sursa(job #3249714)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 17 octombrie 2024 16:32:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax=2e6+3, mod=100076969, baz=103;
int hsa=0, pwr[nmax], inv[nmax], sp[nmax];
vector <int> ras;

int convert(char c)
{
    if(c-'0'<=9) return (c-'0'+1);
    if(c-'A'<=26) return (c-'A'+11);
    return (c-'a'+11+26);
}

int exp(int x, int put)
{
    if(put==0) return 1;
    int nr=exp(x, put/2)%mod;
    if(put%2==0) return 1LL*nr*nr%mod;
    return 1LL*nr*nr%mod*x%mod;
}

signed main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");

    int start=exp(baz, mod-2);
    inv[0]=1;
    inv[1]=start;
    for(int i=2; i<nmax; i++)
    {
        inv[i]=1LL*inv[i-1]*start%mod;
    }
    pwr[0] = 1;
    pwr[1]=baz;
    for(int i=2; i<nmax; i++)
    {
        pwr[i]=(1LL*pwr[i-1]*baz)%mod;
    }

    string s, s2;
    cin>>s>>s2;
    for(int i=0; i<s.size(); i++)
    {
        int x=convert(s[i]);
        (hsa+=(1LL*x*pwr[i])%mod)%=mod;
    }
    int lg=s.size(), n=s2.size();
    sp[0]=convert(s2[0]);
    for(int i=1; i<s2.size(); i++)
    {
        sp[i]=(1LL*sp[i-1]+1LL*convert(s2[i])*pwr[i])%mod;
    }
    int ans=0;
    for(int i=lg-1; i<n; i++)
    {
        int sum=1LL*(sp[i]-(i - lg >= 0 ? sp[i-lg] : 0)+mod)%mod*inv[i-lg+1]%mod;
        if(sum==hsa)
        {
            if(ans<1000)
                ras.push_back(i-lg+1);
            ans++;
        }
    }
    cout<<ans<<'\n';
    for(auto i:ras) cout<<i<<' ';

    return 0;
}