Cod sursa(job #2772702)

Utilizator PalcPalcu Stefan Palc Data 2 septembrie 2021 13:29:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define P 9987671
#define Q 9981121
using namespace std;

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

char a[2000005], b[2000005];
int n;
int cod[256], poz[1005], m;

int main()
{
    int i, j;
    int h, H, h1, h2, pw, PW, cnt;
    j = 0;
    for (i = '0'; i <= '9'; i++)
        cod[i] = j++;
    for (i = 'a'; i <= 'z'; i++)
        cod[i] = j++;
    for (i = 'A'; i <= 'Z'; i++)
        cod[i] = j++;

    fin >> a >> b;
    h = H = 0;
    for (n = 0; a[n] != 0; n++)
    {
        h = (h * 62 + cod[a[n]]) % P;
        H = (H * 62 + cod[a[n]]) % Q;
    }
    pw = PW = 1;
    for (i = 1; i < n; i++)
    {
        pw = pw * 62 % P;
        PW = PW * 62 % Q;
    }

    h1 = h2 = 0;
    cnt = 0;
    for (i = 0; i < n; i++)
    {
        h1 = (h1 * 62 + cod[b[i]]) % P;
        h2 = (h2 * 62 + cod[b[i]]) % Q;
    }
    if (h1 == h && h2 == H)
    {
        cnt++;
        poz[++m] = 0;
    }

    for (i = n; b[i] != 0; i++)
    {
        h1 = ((h1 - cod[b[i - n]] * pw % P + P) * 62 + cod[b[i]]) % P;
        h2 = ((h2 - cod[b[i - n]] * PW % Q + Q) * 62 + cod[b[i]]) % Q;
        if (h1 == h && h2 == H)
        {
            cnt++;
            poz[++m] = i - n + 1;
        }
    }
    fout << cnt << "\n";
    for (i = 1; i <= m; i++)
        fout << poz[i] << " ";
    fin.close();
    fout.close();
    return 0;
}