Cod sursa(job #2696424)

Utilizator cameleonGeorgescu Dan cameleon Data 15 ianuarie 2021 21:11:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;

#define MOD1 100007
#define MOD2 100021
#define B 73

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string a,b;
vector <int> sol;

int main()
{
    fin >> a >> b;

    int cod1=0, cod2=0, p1, p2, c1=0, c2=0, nr = 0, n= a.size();
    cod1 = cod2 = 0;
    p1 = p2 = 1;
    for(unsigned int i = 0; i < a.size(); i++)
    {
        cod1 = (cod1*B % MOD1 + a[i]%MOD1)%MOD1;
        cod2 = (cod2*B % MOD2 + a[i]%MOD2)%MOD2;
        if(i != 0)
            p1 = p1*B %MOD1, p2 = p2*B %MOD2;
    }

    for(unsigned int i = 0 ; i < b.size(); i++)
        if(i < a.size())
        {
            c1 = (c1*B %MOD1 + b[i]%MOD1)%MOD1;
            c2 = (c2*B %MOD2 + b[i]%MOD2)%MOD2;

        }
        else{
            if(c1 == cod1 && c2 == cod2)
                {nr++; if(nr <= 1000) sol.push_back(i-n);}

            c1 = ((c1 + MOD1 - b[i-n]*p1%MOD1)*B%MOD1 + b[i])%MOD1;
            c2 = ((c2 + MOD2 - b[i-n]*p2%MOD2)*B%MOD2 + b[i])%MOD2;
        }

    if(c1 == cod1 && c2 == cod2)
            {
                nr++;
                if(nr <= 1000) sol.push_back(b.size()-n);
            }

    fout << nr <<'\n';
    for(unsigned int i = 0; i < sol.size(); i++)
        fout << sol[i] << " ";

    return 0;

}