Cod sursa(job #2774655)

Utilizator sergioneUngureanu Sergiu sergione Data 12 septembrie 2021 10:31:52
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 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 = 6667;


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]<<" ";
        }


}