Cod sursa(job #2632448)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 3 iulie 2020 12:52:20
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <vector>

using namespace std;

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

string a, b;

int MOD[2] = {100003, 666013};
int Put[2] = {127, 131};
int Power[2] = {1, 1};
int Val_A[2] = {0, 0};
int Val_B[2] = {0, 0};

int car (char ch) {
    return ch - '0';
}

bool Egal (int a[], int b[], int N) {
    for (int i = 0; i < N; ++ i ) {
        if (a[ i ] != b[ i ]) return false;
    }
    return true;
}

void Solve () {
    if (a.size() > b.size()) {
        g << 0 << '\n';
        return;
    }

    for (int i = 0; i < a.size(); ++ i ) {
        for (int j = 0; j < 2; ++ j ) {
            Val_B[ j ] = (1LL * Val_B[ j ] * Put[ j ] % MOD[ j ] + car(b[ i ])) % MOD[ j ];
            Val_A[ j ] = (1LL * Val_A[ j ] * Put[ j ] % MOD[ j ] + car(a[ i ])) % MOD[ j ];
        }
    }
    for (int i = 1; i < a.size(); ++ i ) {
        for (int j = 0; j < 2; ++ j ) {
            Power[ j ] = (1LL * Power[ j ] * Put[ j ]) % MOD[ j ];
        }
    }

    vector <int> ans;

    if (Egal(Val_A, Val_B, 2))
        ans.push_back(1);

    for (int i = a.size(); i < b.size(); ++ i ) {
        for (int j = 0; j < 2; ++ j ) {
            Val_B[ j ] = (Val_B[ j ] - 1LL * Power[ j ] * car(b[ i - a.size() ]) % MOD[ j ] + MOD[ j ]) % MOD[ j ];
            Val_B[ j ] = (1LL * Val_B[ j ] * Put[ j ] % MOD[ j ] + car(b[ i ])) % MOD[ j ];
        }

        if (Egal(Val_A, Val_B, 2)) {
            ans.push_back(i - a.size() + 1);
        }
    }

    g << ans.size() << '\n';
    for (int i = 0; i < min(1000, (int)ans.size()); ++ i ) {
        g << ans[ i ] << " ";
    }
}

int main()
{
    f >> a >> b;

    Solve();

    return 0;
}