Cod sursa(job #2774665)

Utilizator sergioneUngureanu Sergiu sergione Data 12 septembrie 2021 11:10:22
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX = 2e6 + 5;
const int baza = 29;
const int mod = 1000000007;


vector <int> v;
char a[NMAX], b[NMAX];
int n, m, ha = 0, hsb = 0, cnt;
int main()
{

    in >> (a+1) >> (b+1);

    n = strlen(a+1);

    m = strlen(b+1);

    int puterea = 1;

    for ( int i = 1; i <= n-1; ++i)

        puterea = (puterea * baza) % mod;

    for ( int i =1; i <= n; ++i)
    {

        ha = ((1LL * ha * baza)%mod +  (int)a[i])%mod;


    }

    for ( int i = 1; i <= n; ++i)
    {

        hsb= ((1LL * hsb * baza)%mod +  (int)b[i])%mod;

    }

    if(ha ==hsb)
    {
        ++cnt;
        v.push_back(1);
    }


    int aux = hsb;

    for ( int dr = n+1; dr <= m; ++dr)
    {

        int hb = (aux - ((1LL * (int)b[dr-n] *puterea)%mod) + mod)%mod;

        hb = (1LL*hb * baza)%mod;

        hb = (hb + (int)b[dr])%mod;

        if(ha == hb)
        {

            ++cnt;
            if(v.size() <= 1000)
                v.push_back(dr - n);

        }

        aux = hb;

    }

    out << cnt<<endl;
    for(int i = 0; i < v.size(); ++i)
    {
        out<<v[i]<<" ";
    }


}