Cod sursa(job #2777688)

Utilizator Edyci123Bicu Codrut Eduard Edyci123 Data 23 septembrie 2021 21:38:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define DIM 2000005
#define P 73
#define MOD1 100007
#define MOD2 100021

using namespace std;

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

int n, m, hashA1, hashA2, hashB1, hashB2, nr;
int P1, P2;
char A[DIM], B[DIM];
vector <int> ans;

int main()
{
    f >> A >> B;
    int n = strlen(A);
    int m = strlen(B);

    P1 = P2 = 1;
    for(int i = 0; i < n; i++)
    {
        hashA1 = (hashA1 * P + A[i]) % MOD1;
        hashA2 = (hashA2 * P + A[i]) % MOD2;
        if(i)
        {
            P1 = P1 * P % MOD1;
            P2 = P2 * P % MOD2;
        }
    }

    if(n > m)
    {
        g << 0 << "\n";
        return 0;
    }

    for(int i = 0; i < n; i++)
    {
        hashB1 = (hashB1 * P + B[i]) % MOD1;
        hashB2 = (hashB2 * P + B[i]) % MOD2;
    }

    if(hashA1 == hashB1 && hashA2 == hashB2)
        ans.push_back(0), nr++;


    for(int i = n; i < m; i++)
    {
        hashB1 = ((hashB1 + MOD1 - (B[i - n] * P1) % MOD1) * P % MOD1 + B[i]) % MOD1;
        hashB2 = ((hashB2 + MOD2 - (B[i - n] * P2) % MOD2) * P % MOD2 + B[i]) % MOD2;
        if(hashA1 == hashB1 && hashA2 == hashB2 && nr <= 1000)
            ans.push_back(i - n + 1), nr++;
    }

    g << nr << "\n";
    for(auto k : ans)
        g << k << " ";


    return 0;
}