Cod sursa(job #2533806)

Utilizator betybety bety bety Data 29 ianuarie 2020 18:49:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
#define A 911382323
#define B 972663749
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const long long lim=2e6+3;
vector<long long> sol;
int main()
{
    string a,b;
    long long na,nb,ha=0,hb=0,cnt=0,p=1;
    cin>>a>>b;
    na=a.size(),nb=b.size();
    if(na>nb)
    {
        cout<<0;
        return 0;
    }
    for(long long i=0;i<na;++i)
    {
        ha=(ha*A+a[i]-48)%B;
        hb=(hb*A+b[i]-48)%B;
        p=(p*A)%B;
    }
    if(ha==hb)
    {
        ++cnt;
        sol.push_back(0);
    }
    for(long long i=na;i<nb;++i)
    {
        hb=(hb*A+b[i]-48)%B;
        hb=(hb+B-(p*(b[i-na]-48))%B)%B;
        if(ha==hb)
        {
            ++cnt;
            if(cnt<=1000)
                sol.push_back(i-na+1);
        }
    }
    cout<<cnt<<'\n';
    long long nr=sol.size();
    for(long long i=0;i<nr;++i)
        cout<<sol[i]<<' ';
    return 0;
}