Cod sursa(job #2789453)

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

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define mod 100007
int lna,lnb,cnt,starts[1005];
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)
        {
            ++cnt;
            if(cnt<=1000)
                starts[cnt]=i;
        }
        /*{bool ok=true;
            for(int j=0;j<lna;++j)
                if(a[j]!=b[i+j])ok=false;
            if(ok)
            {
                ++cnt;
                if(cnt<=1000)
                    starts[cnt]=i;
            }
        }*/

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