Cod sursa(job #3300551)

Utilizator stefan05Vasilache Stefan stefan05 Data 16 iunie 2025 23:27:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <cstring>

#define SMAX 2000005
#define ALFMAX 100

using namespace std;

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

const int MOD = 1e9 + 7;

char pattern[SMAX];
char s[SMAX];
int n, m;
int rez[SMAX]; int nr;
int k, i;

bool verif(int);

int main()
{
    fin >> pattern >> s;
    int m = strlen(pattern);
    int n = strlen(s);


    long long int x = 0, y = 0, p = 1;
    for (i = 0; i < m; ++i)
    {
        x = x * ALFMAX % MOD + (pattern[i] - '0'); x %= MOD;
        y = y * ALFMAX % MOD + (s[i] - '0'); y %= MOD;

        if (i < m-1) p *= ALFMAX, p %= MOD;
    }

    if (y == x)
        if (verif(0))
            rez[++nr] = 0;

    for (i = 1; i + m - 1 < n; i++)
    {
        y = ((y - p * (s[i - 1] - '0') % MOD + MOD) * ALFMAX + (s[i + m - 1] - '0')) % MOD;
        if (y == x)
            if (verif(i))
                if (nr <= 1000) rez[++nr] = i;
                else nr++;
    }

    fout << nr << '\n';
    for (i = 1; i <= min(nr, 1000); ++i)
        fout << rez[i] << ' ';
    fout << '\n';
    return 0;
}

bool verif(int pos)
{
    for (int i = 0; i < m; ++i)
        if (s[pos + i] != pattern[i])
            return 0;
    return 1;
}