Cod sursa(job #3001650)

Utilizator tomaionutIDorando tomaionut Data 13 martie 2023 20:23:32
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
#define P 100007
#define Q 100021
using namespace std;

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

char s1[2000005], s2[2000005];
int n, m, sol[1005], len;

int main()
{
    int i, cod1, cod2, cod3, cod4, pow1, pow2;
    fin >> (s1 + 1) >> (s2 + 1);
    n = strlen(s1 + 1);
    m = strlen(s2 + 1);
    cod1 = cod2 = cod3 = cod4 = 0;
    pow1 = pow2 = 1;
    for (i = 1; i <= n; i++)
    {
        cod1 = (cod1 * 73 + s1[i]) % P;
        cod2 = (cod2 * 73 + s1[i]) % Q;
        cod3 = (cod3 * 73 + s2[i]) % P;
        cod4 = (cod4 * 73 + s2[i]) % Q;
        if (i != 1)
        {
            pow1 = pow1 * 73 % P;
            pow2 = pow2 * 73 % Q;
        }
    }
    if (cod1 == cod3 and cod2 == cod4)
        sol[++len] = 1;

    for (i = n + 1; i <= m; i++)
    {
        cod3 = ((cod3 - pow1 * s2[i - n] % P + P) * 73 + s2[i]) % P;
        cod4 = ((cod4 - pow2 * s2[i - n] % Q + Q) * 73 + s2[i]) % Q;
        //cout << cod1 << " " << cod3 << " " << cod2 << " " << cod4 << "\n";
        if (cod1 == cod3 and cod2 == cod4 and len < 999)
            sol[++len] = i - n;
    }
    fout << len << "\n";
    for (i = 1; i <= min(len, 1000); i++)
        fout << sol[i] << " ";



    return 0;
}