Cod sursa(job #2789449)

Utilizator andreibazavanAndrei Bazavan andreibazavan Data 27 octombrie 2021 15:51:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define mod 100007
int lna,lnb,cnt,starts[2000005];
unsigned long long cod;
string a,b;
int main()
{
    fin>>a;
    fin>>b;
    lna=a.size();
    unsigned long long pow=1;
    for(int i=lna-1;i>=0;--i)
    {
        cod=(cod+(a[i]-'0')*pow)%mod;
        pow*=52;
    }
    lnb=b.size();
    for(int i=0;i<lnb-lna+1;++i)
    {
        unsigned long long codb=0;
        unsigned long long pow=1;
        for(int j=i+lna-1;j>=i;--j)
        {
         codb=(codb+(b[j]-'0')*pow)%mod;
         pow*=52;
        }
        if(cod==codb)
        {bool ok=true;
            for(int j=0;j<lna;++j)
                if(a[j]!=b[i+j])ok=false;
            if(ok)starts[++cnt]=i;
        }

    }
    fout << cnt << '\n';
    for(int i=1;i<=cnt;++i)
        fout << starts[i] << ' ';
    fout<<'\n';
    return 0;
}