Cod sursa(job #3144410)

Utilizator AdiFBubuBubuianu Adrian AdiFBubu Data 7 august 2023 22:24:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

#define NMAX 2000005
#define P 130
#define MOD1 100001
#define MOD2 100027

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

int vA1, vA2, vB1, vB2;
int P1 = 1, P2 = 1;
int nr;
char A[NMAX], B[NMAX];
bool p[NMAX];

int main()
{
    f.getline(A, NMAX);
    f.getline(B, NMAX);
    int na = strlen(A), nb = strlen(B);

    if(na > nb)
    {
        g << 0;
        return 0;
    }

    for(int i = 0; i < na; i ++)
    {
        if(i != 0)
        {
            P1 = (P1 * P) % MOD1;
            P2 = (P2 * P) % MOD2;
        }
        vA1 = ( (vA1 * P) % MOD1 + A[i] ) % MOD1;
        vA2 = ( (vA2 * P) % MOD2 + A[i] ) % MOD2;
    }

    for(int i = 0; i < na; i ++)
    {
        vB1 = ( (vB1 * P) % MOD1 + B[i] ) % MOD1;
        vB2 = ( (vB2 * P) % MOD2 + B[i] ) % MOD2;
    }

    if(vA1 == vB1 && vA2 == vB2)
    {
        nr ++;
        p[0] = 1;
    }

    for(int i = na; i < nb; i ++)
    {
        vB1 = ( ( vB1 - (B[i - na] * P1) % MOD1 + MOD1 ) * P + B[i] ) % MOD1;
        vB2 = ( ( vB2 - (B[i - na] * P2) % MOD2 + MOD2 ) * P + B[i] ) % MOD2;

        if(vA1 == vB1 && vA2 == vB2)
        {
            nr ++;
            p[i - na + 1] = 1;
        }
    }

    g << nr << '\n';

    int val = 0;
    for(int i = 0; val != nr && val != 1000; i ++)
        if(p[i] == 1)
        {
            val ++;
            g << i << " ";
        }

    return 0;
}