Cod sursa(job #2928359)

Utilizator TraianQTraianQ TraianQ Data 22 octombrie 2022 20:23:25
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
using namespace std;
int positions[2000005];
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string a,b;
    long long nr=0,nrB=0,put=1,counter=0;
    cin>>a>>b;
    for(int i=0;i<a.size();i++)
    {
        nr=(long long)((nr*128+a[i])%1000000007);
        nrB=(long long)((nrB*128+b[i])%1000000007);
        put=(long long)((put*128)%1000000007);
    }
    for(int i=a.size();i<b.size();i++)
    {
        if(nrB==nr)
            counter++,positions[counter]=i;
        nrB=(long long)((nrB*128+b[i])%1000000007);
        nrB=(long long)((nrB-put*(b[i-a.size()]))%1000000007);
        if(nrB<0)
            nrB+=1000000007;
    }
    if(nrB==nr)
        counter++;
    cout<<counter<<'\n';
    for(int i=1;i<=max(counter,1000LL);i++)
        cout<<positions[i]-a.size()<<" ";
    return 0;
}