Cod sursa(job #3341995)

Utilizator tudoor_balasescuBalasescu Tudor tudoor_balasescu Data 22 februarie 2026 13:39:11
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <cstring>
#define LGMAX 2000005
#define MOD1 1000000007
#define MOD2 1000000013
#define P 97

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[LGMAX], b[LGMAX];
int lg1, lg2, k, nr, st[1005], hasha1, hasha2, hashb1, hashb2, p1, p2;
int Poz(char x, int MOD)
{
    int poz=x-'A'+1;
    return poz%MOD;
}
int main()
{

    fin>>a>>b;
    lg1=strlen(a);
    lg2=strlen(b);
    p1=p2=1;
    for(int i=0; i<lg1; i++)
    {
        hasha1=(hasha1*P%MOD1 + Poz(a[i], MOD1))%MOD1;
        hasha2=(hasha2*P%MOD2 + Poz(a[i], MOD2))%MOD2;
        hashb1=(hashb1*P%MOD1 + Poz(b[i], MOD1))%MOD1;
        hashb2=(hashb2*P%MOD2 + Poz(b[i], MOD2))%MOD2;
        if(i)
        {
            p1=(p1*P)%MOD1;
            p2=(p2*P)%MOD2;
        }
    }

    if(hasha1==hashb1 && hasha2==hashb2)
        st[++nr]=0;

    for(int i=lg1; i<lg2; i++)
    {
        hashb1=((hashb1+MOD1-p1*Poz(b[i-lg1], MOD1)%MOD1)%MOD1*P%MOD1+Poz(b[i], MOD1))%MOD1;
        hashb2=((hashb2+MOD2-p2*Poz(b[i-lg1], MOD2)%MOD2)%MOD2*P%MOD2+Poz(b[i], MOD2))%MOD2;
        //hash=(hash-p*Poz(b[i-lg1]))*P+Poz(b[i])
        if(hasha1==hashb1 && hasha2==hashb2)
            st[++nr]=i-lg1+1;
    }

    fout<<nr<<'\n';
    for(int i=1; i<=nr && i<=1000; i++)
        fout<<st[i]<<' ';
    return 0;
}