Cod sursa(job #3001676)

Utilizator brianna_enacheEnache Brianna brianna_enache Data 13 martie 2023 20:41:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#define mod1 100007
#define mod2 100021
using namespace std;

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

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

int main()
{
    in >> a >> b;
    int i, j, hA, HA, hB, HB, p, P, cnt = 0;
    hA = HA = hB = HB = 0;
    p = P = 1;
    j = 0;
    n = strlen(a);
    for(i = 0; i < n; i++)
    {
        hA = (hA * 73 + a[i]) % mod1;
        HA = (HA * 73 + a[i]) % mod2;
        hB = (hB * 73 + b[i]) % mod1;
        HB = (HB * 73 + b[i]) % mod2;
    }
    for(i = 1; i < n; i++)
    {
        p = p * 73 % mod1;
        P = P * 73 % mod2;
    }
    if(hA == hB and HA == HB)
    {
        cnt++;
        poz[++m] = 0;
    }
    for(i = n; b[i] != 0; i++)
    {
        hB = ((hB - b[i - n] * p % mod1 + mod1) * 73 + b[i]) % mod1;
        HB = ((HB - b[i - n] * P % mod2 + mod2) * 73 + b[i]) % mod2;
        if(hA == hB and HA == HB)
        {
            cnt++;
            if(m < 1000) poz[++m] = i - n + 1;
        }
    }
    out << cnt << "\n";
    for(i = 1; i <= m; i++)
        out << poz[i] << " ";
    in.close();
    out.close();
    return 0;
}