Cod sursa(job #3001496)

Utilizator PalcPalcu Stefan Palc Data 13 martie 2023 18:38:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
#define P 9987671
#define Q 9981121
using namespace std;

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

int n, m, h, H, h1, H1, pwd, PWD, nr_apar;
int cod[256], poz[1005];
char a[2000005], b[2000005];

void Coduri()
{
    int cnt = 0;
    for (int x = '0'; x <= '9'; x++)
        cod[x] = cnt++;
    for (int x = 'A'; x <= 'Z'; x++)
        cod[x] = cnt++;
    for (int x = 'a'; x <= 'z'; x++)
        cod[x] = cnt++;
}

int main()
{
    fin >> a;
    fin >> b;
    n = strlen(a);
    m = strlen(b);
    Coduri();
    for (int i = 0; i < n; i++)
    {
        h = (h * 62 + cod[a[i]]) % P;
        H = (H * 62 + cod[a[i]]) % Q;
        h1 = (h1 * 62 + cod[b[i]]) % P;
        H1 = (H1 * 62 + cod[b[i]]) % Q;
    }
    if (h == h1 && H == H1)
        poz[++nr_apar] = 0;
    pwd = PWD = 1;
    for (int i = 1; i < n; i++)
    {
        pwd = (pwd * 62) % P;
        PWD = (PWD * 62) % Q;
    }
    for (int i = n; i < m; i++)
    {
        h1 = ((h1 - cod[b[i - n]] * pwd % P + P) * 62 + cod[b[i]]) % P;
        H1 = ((H1 - cod[b[i - n]] * PWD % Q + Q) * 62 + cod[b[i]]) % Q;
        if (h == h1 && H == H1)
        {
            nr_apar++;
            if (nr_apar <= 1000)
                poz[nr_apar] = i - n + 1;
        }
    }
    fout << nr_apar << "\n";
    for (int i = 1; i <= nr_apar; i++)
        fout << poz[i] << " ";
    fout << "\n";
    fin.close();
    fout.close();
    return 0;
}