Cod sursa(job #3341998)

Utilizator tudoor_balasescuBalasescu Tudor tudoor_balasescu Data 22 februarie 2026 13:52:07
Problema Potrivirea sirurilor Scor 72
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <fstream>
#include <cstring>
#define LGMAX 2000005
/*
#define MOD1 1000000007
#define MOD2 1000000013
#define P 97
*/
#define MOD1 100007
#define MOD2 100021
#define P 73

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
struct Hash1
{
    int a;
    bool operator +(const Hash1 &other) const
    {
            return (a+other.a)%MOD1;
    }
    bool operator -(const Hash1 &other) const
    {
            return (a-other.a+MOD1)%MOD1;
    }
    bool operator *(const Hash1 &other) const
    {
            return (a*other.a)%MOD1;
    }
};

struct Hash2
{
    int a;
    bool operator +(const Hash2 &other) const
    {
            return (a+other.a)%MOD2;
    }
    bool operator -(const Hash2 &other) const
    {
            return (a-other.a+MOD2)%MOD2;
    }
    bool operator *(const Hash2 &other) const
    {
            return (a*other.a)%MOD2;
    }
};

char a[LGMAX], b[LGMAX];
int lg1, lg2, k, nr, st[1005];
int hasha1, hashb1, p1;
int hasha2, hashb2, 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);

    if(lg1>lg2)
    {
        fout<<0;
        return 0;
    }
    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;
}