Cod sursa(job #3214353)

Utilizator tomaionutIDorando tomaionut Data 14 martie 2024 08:36:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#define P 123457
#define Q 777013
#define BASE 73
using namespace std;

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

char s[2000005], s2[2000005];
int sol, nr[1005], k, cod1, cod2, cod3, cod4;

bool Matchy()
{
    return (cod1 == cod3 and cod2 == cod4);
}

int main()
{
    int i, n, pow1 = 1, pow2 = 1;
    fin >> s >> s2;
    n = strlen(s);
    cod1 = cod2 = cod3 = cod4 = 0;
    for (i = 0; s[i]; i++)
    {
        cod1 = (cod1 * BASE + s[i]) % P;
        cod2 = (cod2 * BASE + s[i]) % Q;
        cod3 = (cod3 * BASE + s2[i]) % P;
        cod4 = (cod4 * BASE + s2[i]) % Q;
        if (i)
        {
            pow1 = pow1 * BASE % P;
            pow2 = pow2 * BASE % Q;
        }
    }

    if (Matchy())
    {
        sol++;
        nr[++k] = 0;
    }

    for (; s2[i]; i++)
    {
        cod3 = ((cod3 - pow1 * s2[i - n] % P + P) * BASE + s2[i]) % P;
        cod4 = ((cod4 - pow2 * s2[i - n] % Q + Q) * BASE + s2[i]) % Q;
        if (Matchy())
        {
            sol++;
            if (k < 1000)
            nr[++k] = i + 1 - n;
        }
    }

    fout << sol << "\n";
    for (i = 1; i <= k; i++)
        fout << nr[i] << " ";

    return 0;
}